이 문제를 DFS, Backtracking 으로 풀어야겠다고 생각했다. 예를 들어 오른쪽으로 이동하는 연산을 했을 때 계속 움직임을 진행하다가 더 이상 움직일 수 없을 때 다시 돌아와서 왼쪽으로 이동하고.. 그런데 하다 보니까 뭔가 잘못됨을 깨달고 다른 코드를 참고하였다.
1. Initialize
- 빨간 공과 파란 공의 위치, 현재까지 움직인 개수를 계속 변경해주어야 하기 때문에 이를 구조체로 정의한다
struct INFO { int ry, rx; int by, bx; int cnt = 0; };
- 처음 주어진 공의 정보를
INFO start
에 저장for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (board[i][j] == 'R') start.ry = i, start.rx = j; if (board[i][j] == 'B') start.by = i, start.bx = j; } } start.cnt=0;
int visited[][][][]
에는 빨간 공의 좌표, 파란 공의 좌표를 차례대로 넣어주어 이 위치에 방문된 적이 있는가를 표시한다.
보드의 가로 세로는 최대 10이기 때문에 메모리는 크게 신경 안 써도 될 거 같다
2. bfs () - 실제로 구슬 굴리기
queue<INFO> q
를 만들고 처음 빨간, 파란공의 위치를 저장한INFO start
를 넣고 4방향으로 이동해보며 탐색한다- 문제에서 10번 이하로 움직여야 한다고 했으므로
cnt>10
이면 종료if (cur.cnt > MAX) break;
- 빨간 구슬의 다음 위치가 구멍이고, 파란색의 다음 위치가 구멍이 아닐 때는 최적의 해를 찾은 것이므로 현재의
cnt
를 returnif (board[cur.ry][cur.rx] == HOLE && board[cur.by][cur.bx] != HOLE) { ret = cur.cnt; break; }
- 구슬을 이동하려는 방향으로 이동하는데, 벽이 아니고 구멍이 아닐 때까지 계속 이동한다. 이동한 곳이 벽이면 한 칸 뒤로 왔던 곳으로 이동한다.
while (1) { if (board[nx_ry][nx_rx] != WALL && board[nx_ry][nx_rx] != HOLE) { nx_ry += dy[dir]; nx_rx += dx[dir]; } else { if (board[nx_ry][nx_rx] == WALL) { nx_ry -= dy[dir]; nx_rx -= dx[dir]; } break; } }
- 빨간, 파란 구슬을 모두 움직였는데 위치가 같고 구멍이 아니라면 구슬 중 더 뒤에 있던 구슬은 한 칸 뒤로 움직여야 한다. 그림으로 예를 들어보면
- 여기서 움직인 위치와 원래 파란색, 빨간색 구슬의 위치의 차를 구해보면 B가 더 크다는 것을 알 수 있다. 위치의 차가 더 크다는 것은 더 멀리 있었다는 뜻이므로 한 칸 뒤로 보내준다
if (nx_ry == nx_by && nx_rx == nx_bx) { if (board[nx_ry][nx_rx] != HOLE) { int red_dist = abs(nx_ry - cur.ry) + abs(nx_rx - cur.rx); int blue_dist = abs(nx_by - cur.by) + abs(nx_bx - cur.bx); if (red_dist > blue_dist) { nx_ry -= dy[dir]; nx_rx -= dx[dir]; } else { nx_by -= dy[dir]; nx_bx -= dx[dir]; } } }
- 이 움직인 위치가 한 번도 방문된 적이 없다면
queue
에 넣어주어 다시 탐색을 반복한다
전체코드
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAX = 10; const char EMPTY = '.'; const char WALL = '#'; const char HOLE = 'O'; int N, M; char board[MAX + 1][MAX + 1]; int visited[MAX][MAX][MAX][MAX] = { 0, }; int dy[] = { 0,0,1,-1 }; int dx[] = { 1,-1,0,0 }; struct INFO { int ry, rx; int by, bx; int cnt = 0; }; INFO start; int bfs() { int ret=-1; queue<INFO> q; q.push(start); visited[start.ry][start.rx][start.by][start.bx] = 1; while (!q.empty()) { INFO cur = q.front(); q.pop(); if (cur.cnt > MAX) break; if (board[cur.ry][cur.rx] == HOLE && board[cur.by][cur.bx] != HOLE) { ret = cur.cnt; break; } for (int dir = 0; dir < 4; dir++) { int nx_ry = cur.ry; int nx_rx = cur.rx; int nx_by = cur.by; int nx_bx = cur.bx; while (1) { if (board[nx_ry][nx_rx] != WALL && board[nx_ry][nx_rx] != HOLE) { nx_ry += dy[dir]; nx_rx += dx[dir]; } else { if (board[nx_ry][nx_rx] == WALL) { nx_ry -= dy[dir]; nx_rx -= dx[dir]; } break; } } while (1) { if (board[nx_by][nx_bx] != WALL && board[nx_by][nx_bx] != HOLE) { nx_by += dy[dir]; nx_bx += dx[dir]; } else { if (board[nx_by][nx_bx] == WALL) { nx_by -= dy[dir]; nx_bx -= dx[dir]; } break; } } if (nx_ry == nx_by && nx_rx == nx_bx) { if (board[nx_ry][nx_rx] != HOLE) { int red_dist = abs(nx_ry - cur.ry) + abs(nx_rx - cur.rx); int blue_dist = abs(nx_by - cur.by) + abs(nx_bx - cur.bx); if (red_dist > blue_dist) { nx_ry -= dy[dir]; nx_rx -= dx[dir]; } else { nx_by -= dy[dir]; nx_bx -= dx[dir]; } } } if (visited[nx_ry][nx_rx][nx_by][nx_bx] == 0) { visited[nx_ry][nx_rx][nx_by][nx_bx] = 1; INFO next; next.ry = nx_ry; next.rx = nx_rx; next.by = nx_by; next.bx = nx_bx; next.cnt = cur.cnt + 1; q.push(next); } } } return ret; } void init() { cin >> N >> M; for (int i = 0; i < N; i++) cin >> board[i]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (board[i][j] == 'R') start.ry = i, start.rx = j; if (board[i][j] == 'B') start.by = i, start.bx = j; } } start.cnt=0; } int main() { init(); cout << bfs() << endl; return 0; }
코드를 뜯어보면 쉬워보이지만 INFO
를 구조체로 만들어 INFO
를 담는 queue
를 만드는 것, visited
를 체크하기 위해 4차원 벡터를 만드는 것, 두 구슬을 겹치지 않게 만드는 것 등. 구현이 복잡하다..