[백준]13460 구슬 탈출2

백준 13460 구슬 탈출 2

위 문제는 삼성 SW역량 테스트에 나왔던 문제이다.

빨간 구슬과 파란 구슬을 동시에 움직여야 해서 예외처리를 할게 많아 구현이 까다로운 문제였다.

https://na982.tistory.com/82?category=145346 블로그를 참고해서 풀었다.

1. 문제

문제링크

2. 접근법

• 문제 접근
  • 빨간 구슬과 파란 구슬을 동시에 움직여야 하고 몇 번 움직였는지 알아야 하므로 각 구슬의 위치와 몇 번 움직였는지에 대한 정보를 담기 위해 구조체를 하나 선언한다.
  • 각 구슬의 위치를 기억하기 위해 위 구조체로 이루어진 큐를 하나 선언하고 BFS를 돌리면 최소 몇번만에 빨간 구슬을 빼낼 수 있는지 구할 수 있다.
  • 구슬은 상, 하, 좌, 우로 벽('#')이 있을때까지 움직일 수 있으므로 구슬의 위치에 벽(#)이 없고 구멍(O)이 아닐때 각 구슬을 벽이 있을때까지 while문을 돌리며 움직여 준다. 
  • 여기서 주의해야 할 점은 상, 하, 좌, 우로 움직일때 두 구슬이 같은 위치에 존재하게 되는 경우 예외처리를 해줘야 한다는 점이다.
  • 위의 경우, 각 구슬의 이전 위치에서 현재 위치로 이동한 거리가 더 짧은 구슬을 한칸 뒤로 이동시키면 된다.

3. 코드

#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<fstream>
#include<queue>

using namespace std;
char map[10][11];	//문자열의 끝 종료지점을 받기 위해 11로 선언 함
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1};

struct INFO
{
	int rY, rX;
	int bY, bX;
	int cnt;
};
INFO start;
int BFS()
{
	queue<INFO> q;
   	int checked[10][10][10][10] = {0, };
	int res = -1;
	q.push(start);
	checked[start.rY][start.rX][start.bY][start.bX] = 1;
	while (!q.empty())
	{
		INFO curr = q.front();
		q.pop();

		if (curr.cnt > 10)
			break;
		if (map[curr.rY][curr.rX] == 'O' && map[curr.bY][curr.bX] != 'O')
		{
			res = curr.cnt;
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int next_ry = curr.rY;
			int next_rx = curr.rX;
			int next_by = curr.bY;
			int next_bx = curr.bX;
			while (1)
			{
				if (map[next_ry][next_rx] != '#' 
                			&& map[next_ry][next_rx] != 'O')
				{
					next_ry += dy[i];
					next_rx += dx[i];
				}
				else
				{
					if (map[next_ry][next_rx] == '#')
					{
						next_ry -= dy[i];
						next_rx -= dx[i];
					}
					break;
				}
			}
			while (1)
			{
				if (map[next_by][next_bx] != '#' 
                			&& map[next_by][next_bx] != 'O')
				{
					next_by += dy[i];
					next_bx += dx[i];
				}
				else
				{
					if (map[next_by][next_bx] == '#')
					{
						next_by -= dy[i];
						next_bx -= dx[i];
					}
					break;
				}
			}
			if (next_by == next_ry && next_rx == next_bx)
			{
				if (map[next_ry][next_rx] != 'O')
				{
					int red_dis = abs(next_ry - curr.rY) 
                    						+ abs(next_rx - curr.rX);
					int blue_dis = abs(next_by - curr.bY) 
                    						+ abs(next_bx - curr.bX);
					if (red_dis > blue_dis)
					{
						next_ry -= dy[i];
						next_rx -= dx[i];
					}
					else
					{
						next_by -= dy[i];
						next_bx -= dx[i];
					}
				}
			}

			if (checked[next_ry][next_rx][next_by][next_bx] == 0)
			{
				checked[next_ry][next_rx][next_by][next_bx] = 1;
				INFO next;
				next.rY = next_ry;
				next.rX = next_rx;
				next.bY = next_by;
				next.bX = next_bx;
				next.cnt = curr.cnt + 1;
				q.push(next);
			}
		}
	}
	return res;
}
void INPUT()
{
	int N, M;
	scanf("%d %d", &N, &M);
    
	for (int i = 0; i < N; ++i)
	{
		scanf("%s", map[i]);
	}
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (map[i][j] == 'R')
			{
				start.rY = i;
				start.rX = j;
			}
			if (map[i][j] == 'B')
			{
				start.bY = i;
				start.bX = j;
			}
		}
	}
    start.cnt = 0;
}
int main()
{
	int ans = 0;
	INPUT();
	ans = BFS();
	printf("%d\n", ans);
	return 0;
}

4. 시간복잡도

BFS알고리즘의 인접행렬을 이용한 방법은 O(V^2)의 시간복잡도를 가지는데,

여기서 상, 하, 좌, 우 4방향으로 이동할 수 있고 최대 10번까지만 움직일 수 있으므로 총 4^10의 경우의 수를 생각할 수 있다.

그런데 구슬은 처음에만 4방향으로 움직이고 이후에는 이전에 이동한 반대 방향으로 이동하게 되면 이전 위치와 동일해지기 때문에 이전에 이동한 방향은 제외시킨다. 또한 이전에 이동한 똑같은 방향으로는 벽때문에 움직일 수 없기 때문에 제외시킨다.

따라서 총 4*2^9 = 2048의 경우의 수에 보드의 수 10을 곱하면 총 20480의 체크로 문제가 풀린다. 

 

전체 시간복잡도는 O(N)+O(N^2)+O(V^2)이며 여기서 O(V^2)은 위에서 구한 20480이다.

따라서 2초내에 풀기에 충분하다.

5. 결과