백준 13460 구슬 탈출 2

1. 째로탈출 완전 시뮬 문제라고 생각했는데 2. 큐로 푸는 방법이 있었다... 3. 이동하는 방법이 나와있고, 4. 겹쳤을 때는 처리하는 방법 5. 공이 겹치는 경우 처리하는 방법 6. 10번 돌려도 안되는 경우 7. 큐에서 와일문을 2개 돌리는 방법이 나와있습니다. 놀랐다. 내 지식으로 흡수하도록 하겠습니다. 불과 3개월전에 봤을 때, 큐를 쓰는 것보다 단순하게 시뮬구현한 코드가 좋다고 생각했는데, 큐를 활용하는 것이 메모리나 시간활용 부분에서 상당히 효율적이다.

/* 0934 구슬 다시 풀이 큐를 사용합니다. */ #include <iostream> #include <algorithm> #include <queue> using namespace std; #define SIZE 11 // 11 char map[SIZE][SIZE]; int visit[SIZE][SIZE][SIZE][SIZE]; int rx, ry, bx, by; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; struct point { int rx, ry, bx, by; }; int x, y, z, w; int ret, N, M; queue<point> que; int qlen; void problemIn() { cin >> N >> M; for (int i = 0; i < N; i++) { cin >> map[i]; for (int j = 0; j < M; j++) { if (map[i][j] == 'B') { bx = i; by = j; } else if (map[i][j] == 'R') { rx = i; ry = j; } } } } int solve() { que.push({ rx,ry,bx,by }); visit[rx][ry][bx][by] = 1; while (!que.empty()) { qlen = que.size(); while (qlen--) { x = que.front().rx; y = que.front().ry; z = que.front().bx; w = que.front().by; que.pop(); if (map[x][y] == 'O' && map[x][y] != map[z][w]) { return ret; } for (int i = 0; i < 4; i++) { int cx, cy, cz, cw; cx = x, cy = y, cz = z, cw = w; while (map[cx + dx[i]][cy + dy[i]] != '#' && map[cx][cy] != 'O') { cx += dx[i]; cy += dy[i]; } while (map[cz + dx[i]][cw + dy[i]] != '#' && map[cz][cw] != 'O') { cz += dx[i]; cw += dy[i]; } if (cx == cz && cy == cw) { // 겹치면, if (map[cz][cw] == 'O') continue; // 파란공이 빠지면, if ((abs(x - cx) + abs(y - cy)) > (abs(z - cz) + abs(w - cw))) { cx -= dx[i]; cy -= dy[i]; } else { cz -= dx[i]; cw -= dy[i]; } } if (visit[cx][cy][cz][cw]) continue; // 공의 위치가 이전과 동일하면, que.push({ cx,cy,cz,cw }); visit[cx][cy][cz][cw] = 1; } } if (ret == 10) { return -1; } ret++; } return -1; } int main() { problemIn(); cout << solve() << endl; return 0; }