<Baekjoon> #13460 DFS,BFS_구슬 탈출 c++

#13460 구슬탈출
참고

이 문제를 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를 return

if (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차원 벡터를 만드는 것, 두 구슬을 겹치지 않게 만드는 것 등. 구현이 복잡하다..