[백준 19236] 청소년 상어

문제 바로가기

19236번: 청소년 상어

 

푸는 데 너무 힘들었던 문제

아기 상어를 BFS로 풀었던 기억이 있어서 아무 생각 없이 BFS로 풀었다가 호되게 당했다 흑흑

BFS로 하다가 DFS로 바꾸면서 로직 다 꼬이고,, 이럴 땐 그냥 덮고 그 다음날 새 마음 새 뜻으로 풀자.

 

그래서. 이 문제는 BFS로 풀면 안되고 재귀함수를 사용해서 DFS로 풀어야한다.

상어가 갈 수 있는 자리가 여러 곳인데, 상어의 위치를 옮기면 그때마다 물고기의 위치도 다 달라지기 때문에 상어가 움직이기 전의 map을 저장해두고 재귀함수를 빠져나올 때 바뀐 map에 저장해두었던 원 상태의 map을 복사해주는 것이다.

 

map의 상태를 저장해두기 위해서 copy_map() 함수를 사용하였다.

그리고 물고기의 위치를 이동시켜야 하는데, 이는 change_map() 함수에서 수행한다. 1번 물고기부터 16번 물고기까지 swap_fish()를 수행한다. 

 

flag는 상어가 움직일 수 있는지의 여부를 나타낸다. flag == 0 이면, 더 이상 움직일 수 없기 때문에

그 때의 fish(상어가 먹은 물고기 번호 수의 합)가 이 전까지의 fish_cnt보다 크다면 fish_cnt의 값을 변경해준다.

 

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

using namespace std;

int pos[8][2] = { {-1,0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1} };
int fish_cnt = 0;
pair<int, int> map[5][5];

bool isIn(int x, int y)
{
	if (x > 0 && x <= 4 && y > 0 && y <= 4)
	{
		return true;
	}
	return false;
}

void swap_fish(int n)
{
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			if (map[i][j].first == n)
			{
				int nx, ny;
				int new_pos = map[i][j].second;
				int pos_cnt = 0;
				while (1)
				{
					nx = j + pos[new_pos][1];
					ny = i + pos[new_pos][0];

					if (isIn(nx, ny) && map[ny][nx].first != -1)
					{
						map[i][j].second = new_pos;
						pos_cnt = 0;
						break;
					}
					new_pos = (new_pos + 1) % 8;
					pos_cnt++;
				}

				if (pos_cnt == 0)
				{
					if (map[ny][nx].first == 0) {
						map[ny][nx] = map[i][j];
						map[i][j].first = 0;
					}
					else
					{
						pair<int, int> tmp = map[ny][nx];
						map[ny][nx] = map[i][j];
						map[i][j] = tmp;
					}
				}
				return;
			}
		}
	}
}

void change_map()
{
	for (int n = 1; n <= 16; n++)
	{
		swap_fish(n);
	}

}

void copy_map(pair<int, int> new_map[][5], pair<int, int> old_map[][5])
{
	for (int i = 1; i <=4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			new_map[i][j] = old_map[i][j];
		}
	}
}

void dfs(int x, int y, int fish)
{
	pair<int,int> tmp = map[y][x];
	int flag = 0;
	fish += map[y][x].first;
	map[y][x].first = -1;
	
	pair<int, int> new_map[5][5];

	copy_map(new_map, map); //map의 상태를 복사해둠 

	change_map();

	for (int i = 1; i <= 3; i++)
	{
		int nx = x + i * pos[map[y][x].second][1];
		int ny = y + i * pos[map[y][x].second][0];

		if (isIn(nx, ny) && map[ny][nx].first > 0)
		{
			map[y][x].first = 0;
			dfs(nx, ny, fish);
			flag = 1;
		}
	}

	if (flag == 0)
	{
		fish_cnt = max(fish_cnt, fish);
	}

	
	copy_map(map, new_map); //map을 다시 돌려놓기
	map[y][x] = tmp;
	return;
}

int main()
{

	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			int a, b;
			cin >> a >> b;
			map[i][j] = make_pair(a, b - 1);
		}
	}

	dfs(1, 1, 0);

	cout << fish_cnt << endl;
	return 0;

}