[백준 13460] 구슬 탈출 2

문제 바로가기

13460번: 구슬 탈출 2

 

흑흑

너무 힘든 문제여따 ㅜ ㅅ ㅜ

 

애초에 코딩 전에 어떻게 풀 지 생각하는 부분에서 내가 잘못 생각한 게 여러 부분 있었다.

먼저,

나는 빨간 공이 움직일 수 있을 때만 판을 기울인다고 생각했다. 하지만 빨간공이 움직일 공간이 없더라도 파란공이 움직일 수 있으면 그 경우의 수를 고려해주었어야 했다.

 

두번째,

백트래킹 방식으로 구현할 때 파란공이 구멍에 빠지면 바로 return을 했는데, 이 부분에서 문제가 생겼다. 파란공이 구멍에 빠질 경우 다른 방향으로 기울이는 경우로 가야하는데, return을 하니까 함수를 빠져나와 바로 끝나버리는 것이다.

따라서 파란공이 구멍에 빠지는 경우가 아닐 때만 그 함수를 다시 호출하여 한 단계 더 들어가면 되는 것이고, 파란공이 구멍에 빠지는 경우일 때는 함수 호출 없이 배열과 빨간공, 파란공 좌표값을 다시 원래대로 돌려주는 작업만 하면 된다.

 

어려운 문제라 그런지, 백준사이트에 질문이 많이 올라와있었다. 거기에 올려준 반례들 하나씩 넣어보면서 오류를 찾아냈다. 로직을 한번에 제대로 생각해내지 못하면 결국 여러 반례를 넣어서 디버깅하면서 잘못된 부분을 찾아야하는데 이렇게 되면 시간을 너무 많이 잡아먹는다.

근데 이 문제는,,, 고려해줄 부분이 너무 많아서 한번만에 제대로 풀기는 너무 힘든 것 같다. 

 

어쨋든 풀어냈으니 다행이라고 생각할란다 ~ ㅎ!

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int map[10][10];
int pos[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int min_cnt = 11;
int game_cnt;

pair<int, int> red_ball;
pair<int, int> blue_ball;

void copy_map(int orig[][10], int neww[][10])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			neww[i][j] = orig[i][j];
		}
	}
}


void solve(int ry, int rx, int by, int bx, int game_cnt, int prev_dir)
{
	int new_map[10][10];
	copy_map(map, new_map);
	pair<int, int> s_red = {ry, rx};
	pair<int, int> s_blue = { by, bx };
	int tmp_gcnt = game_cnt;

	for (int i = 0; i < 4; i++)
	{
		if (prev_dir >= 0 && ((prev_dir == i) || (prev_dir + 2) % 4 == i))
			continue;
		int choose_r_x = rx + pos[i][1];
		int choose_r_y = ry + pos[i][0];

		int choose_b_x = bx + pos[i][1];
		int choose_b_y = by + pos[i][0];

		if ((map[choose_r_y][choose_r_x] != -1 && map[choose_r_y][choose_r_x] != 2) || (map[choose_b_y][choose_b_x] != -1 && map[choose_b_y][choose_b_x] != 1))//움직일 공간이 있음
		{
			game_cnt++;
			
			while (1)
			{
				int nrx = rx + pos[i][1];
				int nry = ry + pos[i][0];

				int nbx = bx + pos[i][1];
				int nby = by + pos[i][0];

				if (map[nby][nbx] == 3)//게임종료
				{
					game_cnt = -1;
					break;
				}

				if (map[nby][nbx] == 0)
				{
					map[nby][nbx] = 2;
					map[by][bx] = 0;

					bx = nbx;
					by = nby;
				}

				if (map[nry][nrx] == 0)
				{
					map[nry][nrx] = 1;
					map[ry][rx] = 0;

					rx = nrx;
					ry = nry;
				}

				if (map[nry][nrx] == 3)
				{
					map[ry][rx] = 0;
				}

				if (map[nry][nrx] == 3 && map[nby][nbx] == -1)
				{
					min_cnt = min(min_cnt, game_cnt);
					break;
				}

				if (map[nry][nrx] == -1 && map[nby][nbx] == -1)
					break;

				if (map[nry][nrx] == 2 && map[nby][nbx] == -1)
					break;

				if (map[nry][nrx] == -1 && map[nby][nbx] == 1)
					break;

			}

			if (game_cnt > 10)
				return;

			if (game_cnt != -1)
			{
				solve(ry, rx, by, bx, game_cnt, i);
			}
			
			copy_map(new_map, map);
			ry = s_red.first;
			rx = s_red.second;
			by = s_blue.first;
			bx = s_blue.second;
			game_cnt = tmp_gcnt;
		}
	}
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			char tmp;
			scanf("\n%1c", &tmp);
			switch (tmp)
			{
			case '#':
				map[i][j] = -1;
				break;
			case '.':
				map[i][j] = 0;
				break;
			case 'R':
				map[i][j] = 1;
				red_ball = { i, j };
				break;
			case 'B':
				map[i][j] = 2;
				blue_ball = { i, j };
				break;
			case 'O':
				map[i][j] = 3;
				break;
			}
		}
	}

	solve(red_ball.first, red_ball.second, blue_ball.first, blue_ball.second, 0, -1);

	if (min_cnt > 10)
		min_cnt = -1;
	cout << min_cnt << endl;
}