[백준 13460][C++] 구슬 탈출 2

문제

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

13460번: 구슬 탈출 2

[참고 링크]

이 문제는 스스로 풀지 못하였고, 참고한 링크의 코드를 이해한 내용을 바탕으로 설명하였다.

 

풀이 과정

1. 문제 조건에 맞도록 기울여 이동하는 함수를 작성한다.

2. 4방향으로 각각 탐색을 진행하며,

    이동을 통해 빨간 공이 구멍에 들어간 경우 현재까지 기울인 횟수를 출력하고 탐색을 종료한다.

    이때 파란 공이 구멍에 들어간 경우는 실패로 처리한다.

3. 주어진 10번 이내에 정답이 없다면, -1을 출력하고 종료한다.

    

 

세부 풀이

(1)

이동 함수는 비교적으로 간단히 구현할 수 있다. 다음 칸이 움직일 수 없는 벽이거나, 현재의 칸이 구멍인 경우 이동을 멈춘다.

그렇지 않은 경우 정해진 방향으로 이동을 진행하며,  변수 c를 통해 이동 거리를 저장한다.

 

이렇게 저장된 이동 거리는 두 공이 같은 Line에서 이동할 때 위치를 잡는데 이용된다.

예를 들어 아래와 같은 6칸의 상황에서 오른쪽으로 기울여 움직인다고 가정했을 때,

# R B . . . . #

 

move 함수에 의해 R과 B 가 제일 끝 부분으로 이동하여 아래와 같은 형태가 될 것이다.

# . . . . . (R/B) #

 

이렇게 같은 위치에 있는 R, B를 각각 rc와 bc로 이동 거리를 저장해 놓았다.

rc는 5, bc는 4의 값을 가지며 rc 가 더 먼 곳에서 온 것을 알 수 있다.

따라서 R 가 더 먼 곳에서 왔고, R를 왔던 방향의 반대방향으로 한 칸 이동시킨 최종 상태는 아래와 같아진다.

# . . . . R B #

 

이동 거리를 보존하여 이동 후 두 구슬의 위치를 파악할 수 있다.

 

(2)

BFS 탐색의 형태를 코드에서 한눈에 확인할 수 있다. queue를 통해 초기의 좌표를 입력한 뒤 탐색을 진행한다.

초기 좌표에서 이동할 수 있는 방향으로 너비 우선 탐색을 진행하여, 

파란 공이 들어가지 않은 상황에서, 빨간 공만 구멍에 들어간 경우 현재까지 기울인 횟수를 출력하며 return 하도록 구현하였다.

 

탐색 중 종료 상황이 아닌 경우에는, 

현재 좌표에 대한 방문 여부를 체크하고, queue에 현재 위치를 입력한다.

이를 통해 이전과 같은 상황의 중복을 피할 수 있다.

 

(3)

이렇게 구현한 BFS 가 10번 의 탐색 안에 답을 찾아내지 못했다면, while 문을 벗어나 -1을 출력하도록 구현하였다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct bead{ 
	int rx, ry; //빨간 구슬 좌표
	int bx, by;  //파란 구슬 좌표 
	int d;  //기울인 횟수 
};

int n,m;
char board[10][10];
bool visited[10][10][10][10];  //방문 여부 
queue<bead> q;
 
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

//새로운 위치가 벽이 아니고, 현재 구멍의 위치가 아니라면, 이동을 진행한다.
//c에 이동 거리를 기록한다.
void move(int& x, int& y, int& c, int& i){
	while(board[x+dx[i]][y+dy[i]] != '#' && board[x][y] != 'O'){
		x += dx[i];
		y += dy[i];
		c += 1; 
	}
}

void bfs(){
	while(!q.empty()){
		int rx = q.front().rx;
		int ry = q.front().ry;
		int bx = q.front().bx;
		int by = q.front().by;
		int d = q.front().d;
		q.pop();
		
		//기울인 횟수가 10이 넘어가면 탐색 중단.
		if(d>=10) break;
		
		for(int i=0; i<4; i++){
			int nrx=rx, nry=ry, nbx=bx, nby=by;
			int rc=0, bc=0, nd=d+1;
			
			move(nrx, nry, rc, i);
			move(nbx, nby, bc, i);
			
			//파란 공이 이미 구멍에 들어간 경우 다음으로 넘어간다.
			if(board[nbx][nby] == 'O') continue;
			//빨간 공이 구멍에 들어간 경우 탐색을 종료하며, 기울인 횟수를 출력한다.
			if(board[nrx][nry] == 'O'){
				cout<<nd;
				return;
			}
			
			//구슬이 겹쳤을 때 
			if(nrx == nbx && nry == nby){
				//굴릴 때, 이동거리가 더 긴 구슬의 위치를 한칸 뒤로 돌림
				if(rc > bc) nrx -= dx[i], nry -= dy[i];
				else nbx -= dx[i], nby -= dy[i];
			}
			
			//4차원 배열을 통해 이미 방문한 경우라면,
			//이미 방문하여 아닌 경우이므로 continue 해준다.
			if(visited[nrx][nry][nbx][nby]) continue;
			visited[nrx][nry][nbx][nby] = true;
			q.push({nrx, nry, nbx, nby, nd});
		}
	}

	//10번 안에 return되지 않으면 -1 출력
	cout<<-1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int rx=0, ry=0, bx=0, by=0;
	cin>>n>>m;
	
	for(int i=0; i<n; i++){
		string s;
		cin>>s; 
		for(int j=0; j<m; j++) {
			board[i][j] = s[j];
			if(s[j] == 'R') rx = i, ry = j;
			else if(s[j] == 'B') bx = i, by = j;
		}
	}
	
	q.push({rx, ry, bx, by, 0});
	visited[rx][ry][bx][by] = true;
	bfs();
}

 

결과 및 후기

이 문제를 풀 때, 고민 시간이 4시간이 넘어가면서 이 이상의 고민은 비효율적이라고 생각하고 풀이를 찾아보게 되었다.

여러 풀이 중 [참조 링크] 풀이가 정말 깔끔하고 BFS가 적용된 것을 한눈에 확인할 수 있었다. 해당 링크의 포스팅도 다른 곳에서 참고한 코드라고 언급되어 있었다. 4차원 배열의 이용과, BFS의 적용, 이동 거리를 저장하여 긴 구슬을 한 칸 뒤로 이동시키는 개념 등이 문제를 풀며 고민하고 구현하기 어려웠던 부분들이 명쾌하게 작성되어 있었다. 많은 점들을 배울 수 있었다.