[G1] 백준 13460번 구슬 탈출 2 C++ BFS, 구현, 시뮬레이션, 너비 우선 탐색

리뷰

 

설계를 하지 않고 무작정 덤볐다가 호되게 당한 문제, 구현과 시뮬레이션은 둘째치고 생각 못하고 있던 조건들이 많아서 애를 먹었다, 해당 문제를 풀기 전에 문제에 대한 조건을 한번 쭉 정리하는걸 추천한다.

https://www.acmicpc.net/problem/13460

 

문제 풀이

전역변수

• n, m : 2차원 맵 상 행과 열의 크기를 저장할 변수
• sx1, sy1, sx2, sy2 : 빨간색 구슬과 파란색 구슬의 x, y좌표를 저장할 변수
• lst : 맵 정보를 저장할 문자열 배열, 최대 크기가 10이므로 10만큼의 크기를 지정해 주었다.
• v : 방문 처리를 할 4차원 정수 배열, 각각의 요소에 sx1, sy1, sx2, sy2의 위치 저장, 맵의 크가보다 1크게 초기화
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 빨간구슬과 파란구슬의 위치와 움직인 턴을 저장할 구조체, 시뮬레이션 용이다.

1. n, m값을 받아와 n번의 for문으로 맵 정보를 lst에 저장해 준다.
2. 맵 정보를 입력 받으며 구슬을 발견하면 각 변수에 값을 매핑해 주고 현재 자리를 '.'로 바꾸어 준다.
3. 입력이 완료되었다면 bfs함수를 호출해 준다.
4. 구조체 Pos타입 큐를 초기화 해주고 해당 큐에 빨간색 구슬과 파란색 구슬의 위치와 0을 삽입해 준다.
5. 추가로 현재 빨간 구슬과 파란 구슬의 위치를 방문처리 해준다.
6. q가 빌때까지 탐색을 시작하며 만약 현재 시뮬레이션의 횟수가 10회차일 경우 continue 처리해 준다.
7. 4방향 탐색을 통해 구슬의 위치를 적절하게 이동시켜 주어야 한다. 우선 현재 위치를 그대로 복사해 준다.
8. 이동을 시작하기 전에 어떤 구슬부터 이동을 해주어야 할지 정의를 해주어야 한다.
9. 만약 우측 이동일 경우 더 오른쪽에 있는 구슬부터 이동을 해준다. 행이 다르면 상관 없다.
10. 좌측 이동일 경우 더 왼쪽에 있는 구슬부터 이동을 해준다. 마찬가지로 행이 다르면 상관 없다.
11. 위쪽 이동일 경우 더 위에 있는 구슬부터 이동을 해준다. 열이 다르면 상관 없다.
12. 아래쪽 이동일 경우 더 아래에 있는 구슬부터 이동을 해준다 마찬가지로 열이 다르면 상관 없다.
13. flag를 각 구슬마다 초깃값 1로 설정해 주고 더 이상 움직이지 못할 경우 flag를 0으로 만들어 준다.
14. 만약 이동중에 '0' 즉, 출구를 만난다면 위치를 10으로 변경해 주고 flag를 0으로 만들어 준다.
15. 모든 이동을 마치고 만약 현재 위치가 방문처리가 되어있는 경우 continue 처리를 해준다.
16. 파란색 구슬의 위치가 10일 경우 해당 공이 빠져나온 것이므로 continue 처리를 해준다.
17. 빨간색 구슬의 위치가 10일 경우 nt값을 리턴하고 탐색을 중단해 준다. 빨간색 구슬만 탈출한 케이스다.
18. 위 조건에 모두 해당하지 않을 경우 현재 위치를 방문처리 해준 뒤 큐에 다시 삽입해 준다.
19. 큐에 삽입할 때에는 최종 이동한 위치와 시간을 늘려준 상태로 추가를 해주면 된다.
20. 만약 큐가 빌때까지 빨간색 구슬만 탈출하지 못했을 경우 -1을 리턴해 주면 된다. 리턴된 값을 그대로 출력해 준다.

 

참고 사항

1. 모든 구슬은 동시에 시뮬레이션 되어야 한다.
2. 공이 움직이는 순서를 명확하게 정의해 주어야 한다.
3. 방문배열을 맵보다 1크게 해준 것은 공이 0에 달했을때 위치를 10으로 변경하므로 세그먼트 폴트를 방지하기 위함

 

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

int n, m, sx1, sy1, sx2, sy2;
string lst[10];
int v[11][11][11][11] = {0,};
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int rx, ry, bx, by, t;
};

int bfs() {
	queue<Pos> q;
	q.push({ sx1, sy1, sx2, sy2, 0 });
	v[sx1][sy1][sx2][sy2] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int crx = pos.rx, cry = pos.ry, cbx = pos.bx, cby = pos.by, ct = pos.t;
		
		if (ct == 10) continue;
		for (int i = 0; i < 4; i++) {
			int nrx = crx, nry = cry, nbx = cbx, nby = cby, nt = ct + 1;
			int flag1 = 1, flag2 = 1;

			if ((i == 0 && cry >= cby) || (i == 1 && cry < cby) || (i == 2 && crx >= cbx) || (i == 3 && crx < cbx)) {
				while (flag1 || flag2) {
					if (flag1 && 0 <= nrx + dx[i] && nrx + dx[i] < n && 0 <= nry + dy[i] && nry + dy[i] < m && lst[nrx + dx[i]][nry + dy[i]] != '#' && (nrx + dx[i] != nbx || nry + dy[i] != nby)) {
						nrx += dx[i]; nry += dy[i];
						if (lst[nrx][nry] == 'O') {
							nrx = 10, nry = 10;
							flag1 = 0;
						}
					}
					else flag1 = 0;
					if (flag2 && 0 <= nbx + dx[i] && nbx + dx[i] < n && 0 <= nby + dy[i] && nby + dy[i] < m && lst[nbx + dx[i]][nby + dy[i]] != '#' && (nbx + dx[i] != nrx || nby + dy[i] != nry)) {
						nbx += dx[i]; nby += dy[i];
						if (lst[nbx][nby] == 'O') {
							nbx = 10, nby = 10;
							flag2 = 0;
						}
					}
					else flag2 = 0;
				}
			}
			else {
				while (flag1 || flag2) {
					if (flag2 && 0 <= nbx + dx[i] && nbx + dx[i] < n && 0 <= nby + dy[i] && nby + dy[i] < m && lst[nbx + dx[i]][nby + dy[i]] != '#' && (nbx + dx[i] != nrx || nby + dy[i] != nry)) {
						nbx += dx[i]; nby += dy[i];
						if (lst[nbx][nby] == 'O') {
							nbx = 10, nby = 10;
							flag2 = 0;
						}
					}
					else flag2 = 0;
					if (flag1 && 0 <= nrx + dx[i] && nrx + dx[i] < n && 0 <= nry + dy[i] && nry + dy[i] < m && lst[nrx + dx[i]][nry + dy[i]] != '#' && (nrx + dx[i] != nbx || nry + dy[i] != nby)) {
						nrx += dx[i]; nry += dy[i];
						if (lst[nrx][nry] == 'O') {
							nrx = 10, nry = 10;
							flag1 = 0;
						}
					}
					else flag1 = 0;
				}
			}

			if (v[nrx][nry][nbx][nby]) continue;
			if (nbx == 10 && nby == 10) continue;
			if (nrx == 10 && nry == 10) return nt;
			v[nrx][nry][nbx][nby] = 1;
			q.push({ nrx, nry, nbx, nby, nt });
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 'B') {
				sx2 = i, sy2 = j;
				lst[i][j] = '.';
			}
			else if (lst[i][j] == 'R') {
				sx1 = i, sy1 = j;
				lst[i][j] = '.';
			}
		}
	}

	cout << bfs();
}