[삼성 SW 역량 테스트 기출] 구슬 탈출 2

13460번: 구슬 탈출 2

- 강의 들으면서 풀었던 문제인데, 풀이가 너무 복잡해서 이해를 제대로 못 하고 넘어갔다. 이걸 시작으로 여기저기서 찾아볼 수 있는 코딩 테스트 기출 문제를 하루에 1~2개씩 풀어볼까 한다.

-

- 세로, 가로 크기인 N, M의 범위가 3이상 10이하다. 오버 걱정은 안 해도 될듯 하다.

- 보드 정보는 벽(#), 빈칸(.), 빨간 공(R), 파란 공(B), 구멍(O)으로 이루어져 있다.

- 게임의 목표는 빨간 공만 구멍에 넣는 것이다. 파란 공이 같이 들어가면 실패다. 간단하게 이렇게 정리할 수 있다.

빨간공 IN + 파란공 STAY : 성공

빨간공 STAY + 파란공 STAY : 다음 단계로

빨간공 IN + 파란공 IN / 빨간공 STAY + 파란공 IN : 실패

- 이동은 위, 아래, 왼쪽, 오른쪽으로 기울여서 가능하다. 두 공은 겹칠 수 없다는 조건이 있다. 만약 두 공이 같은 라인에 있을 경우, 일단 겹칠 때까지 이동하게 둔 뒤에 각각의 공이 이동한 거리를 생각해서 더 많이 이동한 공의 위치를 한 스텝 뒤로 가게 해줬다.

- 최소 몇번 만에 성공할 수 있는지 구하고, 10번 이하로 성공하지 못하면 -1을 출력해준다.

- BFS를 살짝 변형해서 풀 수 있다. 하지만 그냥 무턱대고 풀면 최솟값을 구할 수 없다. 이 문제의 키포인트는 불필요한 이동의 수를 건너뛰어 주는 것이다.

- 만약 보드를 왼쪽으로 기울였다고 하자. 그럼 그 다음에도 왼쪽을 기울이는 게 의미가 있을까? 이미 왼쪽에 가있기 때문에 불필요한 움직임이 된다. 이를 통해 같은 방향을 연속해서 이동하는 경우는 건너 뛰어도 된다는 것을 알 수 있다.

- 이번엔 보드를 위로 기울였다고 해보자. 그 다음 아래로 기울이면 어떻게 될까? 원래 있던 위치로 다시 돌아갈 것이기 때문에 의미 없는 움직임이 된다. 이전 방향과 반대로 움직이는 경우도 건너 뛰어도 무방한 경우라는 것을 알 수 있다. 처음에는 4가지 방향 모두 가능하지만, 그 다음부터는 2가지 경우씩 존재하므로 가능한 경우의 수는 4*2^9 개라는 것도 알 수 있다. 

- 이를 종합해서, queue에 두 공의 위치와 이동 횟수, 이동 방향을 넣어 조건을 쳐내면서 BFS를 돌려주면 된다. 공의 이동을 체크할 때 구멍에 빠지는지 여부를 체크하고, 그 결과를 바탕으로 다음 STEP을 가져가면 된다. 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
using namespace std;

int n, m;
int rx, ry, bx, by, hx, hy;
vector<string> a;
bool check[10][10][10][10];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

int ans = -1;

void bfs() {
	queue<tuple<int, int, int, int, int, int>> q;
	q.push(make_tuple(rx, ry, bx, by, 0, -1));
	check[rx][ry][bx][by] = true;

	while (!q.empty()) {
		int rrx, rry, bbx, bby, cnt, dir;
		tie(rrx, rry, bbx, bby, cnt, dir) = q.front();
		if (cnt == 10) break; // 10번 이하로 안 끝나면 BREAK
		if (ans != -1) break; // 가장 먼저 나온 답이 최솟값이므로 BREAK
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (cnt != 0 && (i % 2 == dir % 2)) continue; // 첫 이동이 아니고 이전과 같은 방향 OR 반대 방향일 때
			int nrx = rrx + dx[i]; 
			int nry = rry + dy[i];
			int nbx = bbx + dx[i];
			int nby = bby + dy[i];
			bool redIn= false, blueIn = false; // 이동 중 구멍에 빠지는지 확인
			int redCount = 0, blueCount = 0; // 이동 거리 카운트
			while (a[nrx][nry] != '#') {
				redCount += 1;
				if (nrx == hx && nry == hy) {
					redIn = true;
					break;
				}
				nrx += dx[i]; nry += dy[i];
			}
			nrx -= dx[i]; nry -= dy[i];

			while (a[nbx][nby] != '#') {
				blueCount += 1;
				if (nbx == hx && nby == hy) {
					blueIn = true;
					break;
				}
				nbx += dx[i]; nby += dy[i];
			}
			nbx -= dx[i]; nby -= dy[i];

			if (redIn && !blueIn) { // RED IN + BLUE STAY
				ans = cnt + 1;
				break;
			}
			else if (!redIn && !blueIn) { // RED STAY + BLUE STAY
				if (nrx == nbx && nry == nby) { // 겹치면
					if (redCount < blueCount) { // 더 많이 이동한 공의 위치를 한 스텝 뒤로
						nbx -= dx[i]; nby -= dy[i];
					}
					else {
						nrx -= dx[i]; nry -= dy[i];
					}
				}
				if (check[nrx][nry][nbx][nby] == false) {
					check[nrx][nry][nbx][nby] = true;
					q.push(make_tuple(nrx, nry, nbx, nby, cnt + 1, i));
				}
			}
		}
	}
	return;
}

int main() {
	cin >> n >> m;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		a.push_back(s);
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'R') {
				rx = i; ry = j;
			}
			else if (a[i][j] == 'B') {
				bx = i; by = j;
			}
			else if (a[i][j] == 'O') {
				hx = i; hy = j;
			}
		}
	}

	bfs();
	cout << ans << '\n';
	return 0;
}

 

참고 : 백준님 알고리즘 강의