[백준 알고리즘 풀이][C++] 13460: 구슬 탈출 2

기본 개념

https://www.acmicpc.net/problem/13460
이러한 문제를 풀때 가장 기초가 되는 것이 바로 문제에서 주어진 상황을 정확히, 그리도 간결하게 구현하는 부분일 것이다. 구슬 탈출 게임에서 구현해야할 부분은 당연하게도 우선 게임 필드와 필드 조작일 것이다.

기본적인 구현이 끝나면 그 이후는 알고리즘 구현이 필요하다. 본 문제는 BFS, 즉 넓이 우선 탐색 기법을 활용하여 문제를 풀면 빠르게 답을 구할 수 있다. 우선, 주어진 게임 필드의 초기 상태를 그래프의 root로 둔 후, 4가지 방향으로의 필드 조작이 행해진 상태를 각각 4개의 child node로 만든다.

문제가 제시한 최대 depth는 10이므로, 총 4^10 = 1,048,576개의 node가 만들어지게 된다는 말이다.

구현

게임 필드(맵) 구현

필드, 즉 게임 맵은 간단하게 2D int 배열로 구현할 수 있다. 이 경우, 맵 표현은 아래와 같이 정의하도록 한다.

그런 후, 사용자 입력을 받아서 만들어둔 배열에 넣어주면 된다.

int w, h; // w == M, h == N. 이해하기 쉽도록 width와 height로 표기
int map[10][10]; // map[x][y] == (x,y) 좌표의 상황
int rx, ry, bx, by, ox, oy;

cin >> h >> w;

for(int y = 0 ; y < n ; y++) {
	for(int x = 0 ; x < m ; x++) { 
		char input;
		cin >> input;
		if(input == '.') map[x][y] = 0;
		if(input == '#') map[x][y] = 1;
		if(input == 'O') { map[x][y] = 2; ox = x ; oy = y; }
		if(input == 'R') { rx = x ; ry = y; }
		if(input == 'B') { bx = x ; by = y; }
	}
}

게임 로직 구현

우선, 함수를 먼저 만들어보도록 하자.

void move_ball(int map[10][10], int *posx, int *posy, int xdir, int ydir);

이 함수로 현재 게임 맵 상태 map와 공의 위치 posx, posy를 받고 방향 변수 xdir, ydir를 받아서 굴려주는 역할을 할 것이다.

이때, xdir, ydir 변수는 각각 -1, 0, 1중 하나의 값을 가지게 되는 방향 변수이며, 아래와 같이 생각하면 된다.

return값은 존재하지 않지만, posx와 posy를 포인터로 받아서 직접 수정해줄 것이다.

while(map[*posx + xdir][*posy + ydir] == 0) { // 주어진 방향의 다음칸 확인하며 전진
	*posx += xdir;
	*posy += ydir;
}
if(map[*posx + xdir][*posy + ydir] == 2) { // 다음칸이 구멍일 경우, 한칸 더 전진 후 함수 종료
	*posx += xdir;
	*posy += ydir;
}

단순한 원리의 작동 방식이다. 주어진 posx, posy 방향이 빈 공간일 시 해당 방향으로 한칸씩 전진한다. 루프가 끝난 시점에서 해당 방향의 다음칸이 구멍(2)일 경우, 공을 구멍 위에 위치시키고 함수를 종료한다.

자, 이제 기본적인 세팅은 끝났다. 이제 본격적으로 BFS를 적용하여 문제를 풀어보도록 하자.

BFS

참고자료: https://velog.io/@sukong/알고리즘-개념-너비우선탐색BFS-lp8zywtn

우선, 게임판의 상태를 정의해야 한다. 상태 하나하나가 우리의 node가 될 것이기 때문이다. 게임판의 상태를 저장하기 위해서는 우선 변화하는것과 변화하지 않는 것을 구분할 필요가 있다.

구슬 탈출 게임에서 벽과 빈 공간, 그리고 구멍의 위치는 절대 변화하지 않는다. 게임 내에서 변화하는 것은 빨강공과 파랑공의 위치 뿐이다.

즉, 게임의 상태는 빨간공, 파란공의 x값과 y값이 게임의 상태일 것이다. 여기에 추가적으로, 게임의 depth, 즉 움직임 수까지 합쳐서 state를 표현하도록 하자.

typedef struct _state {
	int depth;
	int rx, ry, bx, by;
} State;

이 State를 이제 queue에 넣어서 BFS 알고리즘을 시작해줄 것이다.

queue<State> q;
q.push({1, rx, ry, bx, by});

우선 State queue를 만들어주고 depth는 1, rx, ry, bx, by는 초기 입력된 값으로 넣어주었다.

마지막 준비 작업으로, flag를 만들어줄 것이다. flag는 특정 State가 이미 한번 탐색되었는지 아닌지를 표기하게 하여 탐색 횟수를 최소화하기 위한 방안이다.

bool flag[10][10][10][10];

이로서 모든 준비는 완료되었고, 다음의 과정만 차례로 수행해주면 결과를 얻을 수 있다.

1. queue의 맨 앞 State를 pop해준다.
2. 만약 state.depth == 10일 경우, 루프를 빠져나간다.
3. 만약 flag[state.rx][state.ry][state.bx][state.by]가 true일 경우, 바로 1로 돌아간다. (continue)
4. pop된 State에서 각각 위, 아래, 왼쪽, 오른쪽으로 빨강공과 파랑공에 대하여 각각 move_ball 함수를 동작해준다.
5. move_ball 이후 만약 빨강공과 파랑공의 위치가 동일하고 빨강공과 파랑공이 둘다 같은 위치일 경우, 위치를 조정해준다.
6. 만약 현재 bx == ox && by == oy일 경우, 1로 돌아간다.
7. 만약 현재 rx == ox && ry == oy일 경우, depth가 정답이므로, 루프를 빠져나간다.
8. 각각의 상태 4개를 queue에 넣어주고 1로 돌아간다. (depth는 1을 더해준다)

우리의 최종 목표는 1-4의 상태를 만드는 것이다.

위 로직을 코드로 표현하면 아래와 같다:

int ans = -1; // 정답
int dirs[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; // 방향 변수

while(!q.empty() && ans == -1) { // q에 값이 존재하고 ans가 구해지지 않았을때
	// popup data
	state cur = q.front();
	q.pop();

	if(cur.depth > 10) break;
	cur_rx = cur.rx; cur_ry = cur.ry;
	cur_bx = cur.bx; cur_by = cur.by;

	if(flags[cur_rx][cur_ry][cur_bx][cur_by] == 1) continue;
	flags[cur_rx][cur_ry][cur_bx][cur_by] = 1;


	for(int i = 0 ; i < 4 ; i++) { // 각 방향별로
		// move balls
		int temp_rx = cur_rx, temp_ry = cur_ry,
			temp_bx = cur_bx, temp_by = cur_by;
		move_ball(map, &temp_rx, &temp_ry, dirs[i][0], dirs[i][1]);
		move_ball(map, &temp_bx, &temp_by, dirs[i][0], dirs[i][1]);

		// check result
		if(map[temp_bx][temp_by] == 2) continue; // blue fell into hole

		if(map[temp_rx][temp_ry] == 2) { // red fell into hole
			ans = cur.depth;
		} else { // nothing happened
			if(temp_rx == temp_bx && temp_ry == temp_by) { // 공 위치 조정
				if(i == 0) { if(cur_rx < cur_bx) temp_rx -= 1; else temp_bx -= 1; }
				if(i == 1) { if(cur_rx < cur_bx) temp_bx += 1; else temp_rx += 1; }
				if(i == 2) { if(cur_ry < cur_by) temp_ry -= 1; else temp_by -= 1; }
				if(i == 3) { if(cur_ry < cur_by) temp_by += 1; else temp_ry += 1; }
			}
			q.push({cur.depth + 1, temp_rx, temp_ry, temp_bx, temp_by});
		}
	}

마무리

채점 결과는 깔끔하게 나오고 정답 표기가 되었다.

코드 반복을 줄이기 위하여 방항 변수를 만들어 루프 처리하고 코드를 간편화하였다. 본 문제의 핵심은 BFS를 사용하여 탐색 시간을 얼마나 잘 줄일 수 있는지, 그리고 문제가 제공해준 환경을 걸마나 간결하게 구현할 수 있는지가 포인트였던 것 같다.

본 문제를 DFS로 푸는것 또한 물론 가능하지만 굉장히 비효율적이며, DFS로 푸는 순간 이 문제는 사실상 Brute Force 알고리즘이 되어버린다.

항상 특정 조건을 가장 빨리 달성하는 문제는 대부분 BFS로 먼저 접근해봐야 한다는 것을 명심하자