/* 단, 파란 구슬이 구멍으로 같이 나오면 실패입니다. 최대 10번까지 보드를 조작할 수 있으므로 BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능하고, 한 상태 공간에서 해당 방향으로 최대 max 만큼 이동할 수 있으니, 4의 10승 곱 맥스 엔엠임을 알 수 있습니다. 따라서 각 상태 공간 내에서 한 방향으로 이동할때 1. 빨간 구슬과 팔나 구슬이 일직선 상에 없음 1.1 빨구 가는 길에 구멍이 있는 경우 탈출 성공 1.2 파구 가는 길에 구멍이 있는 경우 탈출 실패 1.3 구멍이 없는 경우 구슬들을 최대한 이동한 후에 큐에 푸시 2. 빨간 구슬 가는 길에 파란 구슬이 있는 경우 2.1 파란 구슬 앞에 구멍이 있는 경우 탈출 성공 2.2 파란 구슬 뒤에 구멍이 있는 경우 탈출 실패 3. 파란 구슬이 가는 길에 빨간 구슬이 있는 경우 3.1 구멍이 있는 경우 -> 탈출 실패 3.2 구멍이 없는 경우 -> 빨간 구슬은 최대한 이동, 빨간 구슬은 한칸 덜 이동한 후 큐에 push. 위의 과정을 bfs 각 상태 공간마다 시행하고 깊이가 10이되면 종료 */ #include <iostream> #include <queue> using namespace std; struct Node { int d, rx, ry, bx, by; }; char mat[10][11]; int n, m; int fx, fy; int dx[] = { -1,1,0,0 }; // 북 남 서 동 int dy[] = { 0,0,-1,1 }; int main() { cin >> n >> m; for (int i = 0; i < n; i++) scanf("%s", mat[i]); int srx, sry, sbx, sby; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 'R') srx = i, sry = j; else if (mat[i][j] == 'B') sbx = i, sby = j; else if (mat[i][j] == 'O') fx = i, fy = j; } } queue<Node> q; q.push({ 0, srx, sry, sbx, sby }); int ans = -1; while (!q.empty()) { int cnt = q.front().d; int rx = q.front().rx; int ry = q.front().ry; int bx = q.front().bx; int by = q.front().by; q.pop(); if (cnt == 10) break; for (int i = 0; i < 4; i++) { // case in red ball int rex = 0; int blue = 0; int nrx, nry; int rmove = 0; nrx = rx + dx[i]; nry = ry + dy[i]; while (mat[nrx][nry] != '#') { rmove++; if (nrx == bx && nry == by) blue = rmove; if (mat[nrx][nry] == 'O') rex = rmove; nrx += dx[i]; nry += dy[i]; } bool bex = false; bool red = false; int nbx, nby; int bmove = 0; nbx = bx + dx[i]; nby = by + dy[i]; while (mat[nbx][nby] != '#') { bmove++; if (nbx == rx && nby == ry) red = true; if (mat[nbx][nby] == 'O') bex = true; nbx += dx[i]; nby += dy[i]; } if (!blue && !red) { if (rex) { ans = cnt + 1; goto print; } else if (bex) { continue; } else { q.push({ cnt + 1, rx + dx[i] * rmove, ry + dy[i] * rmove, bx + dx[i] * bmove, by + dy[i] * bmove }); } } else if (blue) { if (rex) { if (rex < blue) { ans = cnt + 1; goto print; } continue; } else { rmove--; q.push({ cnt + 1, rx + dx[i] * rmove, ry + dy[i] * rmove, bx + dx[i] * bmove, by + dy[i] * bmove }); } } else { if (rex) { continue; } else { bmove--; q.push({ cnt + 1, rx + dx[i] * rmove, ry + dy[i] * rmove, bx + dx[i] * bmove, by + dy[i] * bmove }); } } } } print: printf("%d\n", ans); return 0; } |
일단 경우의 수를 나누어서 풀이하는 과정이 필요합니다. 어디서 인덴트를 넣어서 풀이할지 확실하게 결정하도록 합니다. 그리고 큐를 이용해서 10의 뎁스를 찾는 것 굿, 그리고 프린트를 사용해서 중간에 탈출하도록 사용한 것 굿입니다. 다른 코드도 한번 살펴보도록 하겠습니다. |
최대 10번까지 보드를 좆가할 수 있으므로, BFS 탐색을 이용하여 각 상태 공간에서 상하좌우 4방향으로 한 상태 공간에서 해당 방향으로 최대 엔엠만큼 이동할 수 있으므로 빅오는 4^10&max엔엠 입니다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때, 1. 빨간 구슬과 파란 구슬이 일직선 상에 없을때 1.1 빨간 구슬이 가는 길에 구멍이 있는 경우 -> 탈출 성공 1.2 파란 구슬이 가는 길에 구멍이 있는 경우 -> 탈출 실패 2. 빨간 구슬이 가는 길에 파란 구슬이 있을때 2.1 파란 구슬 앞에 구멍이 있는 경우 탈출 성공 2.2 파란 구슬 뒤에 구멍이 있는 경우 탈출 실패 2.3 구멍이 없는 경우 -> 파란 구슬은 최대한 이동하고, 빨간 구슬은 한 칸 덜 이동한 후에 큐에 push 3. 파란 구슬이 가는 길에 빨간 구슬이 있는 경우 3.1 구멍이 있는 경우 탈출 실패 3.2 구멍이 없는 경우 빨간 구슬은 최대한 이동, 파란 구슬은 한 칸 덜 이동한 후에 큐에 push bfs 각 상태 공간마다 시행하고 깊이가 10이 되면 종료하도록 구현합니다. 깊이가 10이되면 종료하도록 합니다. |