백준 13460번 구슬 탈출 2 C/C++ 풀이

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

13460번: 구슬 탈출 2

 

시뮬레이션 문제를 가볍게 봤다가 큰 코 다친 문제.

 

시뮬레이션 문제에서는 1) 문제 이해, 2)디버깅 을 얼마나 빨리 하는가가 문제 풀이의 속도를 결정 짓는 것 같다.

 

내가 접근한 방식은 재귀함수로 푸는 방식이어서 map을 초기화해주는 대신에 바로 전 단계로 돌려주는 것을 구현을 했어야했는데, 이 과정에서 실수가 많았다.

 

#include <stdio.h>
#include <utility>

using namespace std;

FILE* in = fopen("input.txt", "r");

#define MAX 10

int n, m;
int map[MAX][MAX];
pair<int, int> red;
pair<int, int> blue;
pair<int, int> hole;
int path[100];
bool possible = false;
bool red_enter;
bool blue_enter;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int min = 10;

//기울였을 때 구슬의 움직임을 구현한 함수
void tilt(int idx) {
	pair<int, int> new_red = red;
	pair<int, int> new_blue = blue;
	red_enter = false; blue_enter = false;
	bool together = false;
	while (1 == 1)
	{
		if (map[new_red.first + dx[idx]][new_red.second + dy[idx]] == '#')
			break;
		pair<int, int> tmp = new_red;
		new_red.first += dx[idx]; new_red.second += dy[idx];
		if (map[new_red.first][new_red.second] == 'O')
		{
			red_enter = true;
			map[tmp.first][tmp.second] = '.';
			break;
		}
		if (map[new_red.first][new_red.second] == 'B')
		{
			new_red = tmp;
			together = true;
			break;
		}
		int tmp_int = map[new_red.first][new_red.second];
		map[new_red.first][new_red.second] = map[tmp.first][tmp.second];
		map[tmp.first][tmp.second] = tmp_int;
	}
	red = new_red;
	while (1 == 1)
	{
		if (map[new_blue.first + dx[idx]][new_blue.second + dy[idx]] == '#')
			break;
		pair<int, int> tmp = new_blue;
		new_blue.first += dx[idx]; new_blue.second += dy[idx];
		if (map[new_blue.first][new_blue.second] == 'O')
		{
			blue_enter = true;
			map[tmp.first][tmp.second] = '.';
			break;
		}
		if (map[new_blue.first][new_blue.second] == 'R')
		{
			new_blue = tmp;
			break;
		}
		int tmp_int = map[new_blue.first][new_blue.second];
		map[new_blue.first][new_blue.second] = map[tmp.first][tmp.second];
		map[tmp.first][tmp.second] = tmp_int;
	}
	blue = new_blue;
    //만약 빨간 구슬을 굴릴 때 앞에 있는 파란 구슬 때문에 진행하지 못했을 경우를 대비해서
    //together boolean을 두어 빨간색을 한 번 더 이동시켜준다.
	while (together)
	{
		if (map[new_red.first + dx[idx]][new_red.second + dy[idx]] == '#')
			break;
		pair<int, int> tmp = new_red;
		new_red.first += dx[idx]; new_red.second += dy[idx];
		if (map[new_red.first][new_red.second] == 'O')
		{
			red_enter = true;
			map[tmp.first][tmp.second] = '.';
			break;
		}
		if (map[new_red.first][new_red.second] == 'B')
		{
			new_red = tmp;
			break;
		}
		int tmp_int = map[new_red.first][new_red.second];
		map[new_red.first][new_red.second] = map[tmp.first][tmp.second];
		map[tmp.first][tmp.second] = tmp_int;
	}
	red = new_red;
}

// 재귀함수로 구현한 완전탐색
void dfs(int time) {
	//파란색이 들어갔다면 끝
	if (blue_enter)
	{
		return;
	}
    //파란색이 들어가지 않고 빨간색이 들어갔다면
	else if (red_enter)
	{
    	//우선 가능하다고 알려줌
		possible = true;
        // 최솟값 갱신
		if (min > time)
			min = time;
		return;
	}
    // 최솟값보다 시도한 횟수가 많으면 return
	if (time >= min)
	{
		return;
	}
    // 4방향으로 모두 탐색
	for (int i = 0; i < 4; i++)
	{
    	//전의 상태로 돌려주기 위해 빨간색과 파란색의 위치 정보를 저장
		pair<int, int> restore_red = red; pair<int, int> restore_blue = blue;
		tilt(i);
        //디버깅을 위해 path 배열에 i를 저장
		path[time] = i;
        // 횟수 늘려서 한 번 더 탐색
		dfs(time + 1);
        // 원래 상태로 바꾸기
		red_enter = false; blue_enter = false;
		if (blue != restore_blue)
		{
			if (map[blue.first][blue.second] == 'O')
			{
				map[restore_blue.first][restore_blue.second] = 'B';
				blue = restore_blue;

			}
			else {
				char tmp_char;
				map[restore_blue.first][restore_blue.second] = 'B';
				map[blue.first][blue.second] = '.';
				blue = restore_blue;
			}
		}
		if (red != restore_red)
		{
			if (map[red.first][red.second] == 'O')
			{
				map[restore_red.first][restore_red.second] = 'R';
				red = restore_red;
			}
            // 앞서 블루를 갱신해줬기 때문에 red 자리에 블루가 있을 수 있다.
			else if (map[red.first][red.second] == 'B')
			{
				map[restore_red.first][restore_red.second] = 'R';
				red = restore_red;
			}
			else {
				map[restore_red.first][restore_red.second] = 'R';
				map[red.first][red.second] = '.';
				red = restore_red;
			}
		}
	}

}

int main() {
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			fscanf(in, " %c", &map[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 'R')
				red = make_pair(i, j);
			else if (map[i][j] == 'B')
				blue = make_pair(i, j);
		}
	dfs(0);
	if (!possible)
	{
		printf("-1");
	}
	else
	{
		printf("%d", min);
	}
	return 0;
}