[BOJ/백준 19236/C++] 청소년 상어

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

19236번: 청소년 상어

 

[문제 요약]

- 4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다.

- 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

 

- 오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

 

- 물고기는 번호가 작은 물고기부터 순서대로 이동한다.

 

- 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.

 

- 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면이동을 하지 않는다.

- 그 외의 경우에는 그 칸으로 이동을 한다.

- 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

 

- 물고기의 이동이 모두 끝나면 상어가 이동한다.

- 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다.

- 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.

- 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다.

 - 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

 

- 초기 격자판 상태

- 상어 진입 후(좌), 상어 진입 후 물고기 이동(우)

 

[문제 조건]

- 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다.

- 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다.

- 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

- 시간 제한 : 1초

- 메모리 제한 : 5152MB

 

[문제 풀이]

이번 문제는 구현&시뮬레이션과 백트래킹이 합쳐진 문제다.

 

맨 처음에 상어 진입을 제외하면 한 사이클은 다음과 같은 순서로 돌아간다.

• 물고기 번호가 작은 순서부터 방향에 따라 이동한다. 해당 방향이 격자판을 넘어가거나 상어가 있는 칸일 경우 반시계방향으로 45도 회전 후 이동한다. 만약 모든 방향에 대해서 이동이 불가능하면 이동하지 않는다.
• 상어는 먹은 물고기의 방향으로 움직이면서 해당 방향에 있는 물고기를 하나 잡아 먹는다.

생각보다 단순하게 돌아가지만 생각보다 귀찮은 부분들이 다수 있었다.

 

먼저 필자는 기본적으로 원소가 int인 2차원 배열을 격자판으로 이용하였고 들어있는 정보는 물고기들의 번호다. 그리고 -1은 상어를 의미한다.

또한 물고기들을 관리하기 위해 원소가 Fish인 1차원 배열과 bool형태의 1차원 배열을 이용하였다.

bool 형태의 배열은 해당 인덱스번호가 물고기번호와 같고 그 물고기가 잡아먹혔는지 안먹혔는지를 판단하기 위해 사용한다.

Fish 구조체는 { 방향, {위치} }를 멤버로 갖는 구조체다.

 

물고기들 이동 함수

void move_fish(vector<vector<int>> &mp, vector<bool> &dead_or_live, vector<Fish> &Fishes)
{
	for (int i = 1; i <= 16; i++)
	{
		if (dead_or_live[i] == false) continue;
		for (int j = 0; j < 8; j++)
		{
			int nx = Fishes[i].pos.second + dx[Fishes[i].dir];
			int ny = Fishes[i].pos.first + dy[Fishes[i].dir];
			if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
			{
				Fishes[i].dir = (Fishes[i].dir + 1) % 9;
				if (Fishes[i].dir == 0) Fishes[i].dir++;
				continue;
			}
			//상어가 있을 때
			if (mp[ny][nx] == -1)
			{
				Fishes[i].dir = (Fishes[i].dir + 1) % 9;
				if (Fishes[i].dir == 0) Fishes[i].dir++;
				continue;
			}

			pii tmp = { ny,nx };
			swap_fish(mp, Fishes, tmp , Fishes[i].pos);
			break;
		}
	}
}

- 물고기 이동은 그냥 말 그대로 해당 방향으로 갈 수 있는지 판단하고 갈 수 있다면 그 위치에 있는 물고기와 정보를 바꿔주면 된다. 

- 이때 mp배열 상에서도 숫자를 바꿔주어야 하지만 vector<Fish> 배열에서도 각 물고기의 위치와 방향을 갱신 시켜주어야 한다.

 

상어 이동

void simulation(vector<vector<int>> mp, vector<bool> dead_or_live, vector<Fish> Fishes, Shark shk, int sum)
{
	move_fish(mp, dead_or_live, Fishes);

	vector<pii> eat_list;
	int multiple = 1;
	while (1)
	{
		int nx = shk.pos.second + (dx[shk.dir] * multiple);
		int ny = shk.pos.first + (dy[shk.dir] * multiple);
		if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) break;
		if (mp[ny][nx] == 0) { multiple++; continue; }
		eat_list.push_back({ ny,nx });
		multiple++;
	}
	if (eat_list.size() == 0)
	{
		ans = max(ans, sum);
		return;
	}

	for (int i = 0; i < eat_list.size(); i++)
	{
		Shark new_shark;
		int y = eat_list[i].first; int x = eat_list[i].second;
		int num = mp[y][x];

		new_shark = { Fishes[num].dir, {y,x} };
		dead_or_live[num] = false;
		mp[y][x] = -1;
		mp[shk.pos.first][shk.pos.second] = 0;
		simulation(mp, dead_or_live, Fishes, new_shark, sum + num);
		mp[y][x] = num;
		mp[shk.pos.first][shk.pos.second] = -1;
		dead_or_live[num] = true;
	}
}

- 먼저 상어가 먹을 수 있는 물고기들의 위치 정보를 eat_list에 저장해주고 먹을 물고기 없다면 현재까지 먹은 물고기 번호들의 총합 중 가장 큰 값을 갱신 시키고 return, 있다면 DFS방식으로 계속 진행하는 방법이다.

 

 

[소스 코드]

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

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

typedef struct FISH
{
	int dir;
	pii pos;
}Fish;
typedef struct SHARK
{
	int dir;
	pii pos;
}Shark;

int ans = 0;
int dx[9] = { 0, 0,-1,-1,-1,0,1,1,1 };
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 };

void swap_fish(vector<vector<int>>& mp, vector<Fish>& Fishes, pii a, pii b)
{
	int before_a = mp[a.first][a.second];
	int before_b = mp[b.first][b.second];

	int tmp = mp[a.first][a.second];
	mp[a.first][a.second] = mp[b.first][b.second];
	mp[b.first][b.second] = tmp;

	Fishes[before_a].pos = b;
	Fishes[before_b].pos = a;
}

void move_fish(vector<vector<int>> &mp, vector<bool> &dead_or_live, vector<Fish> &Fishes)
{
	for (int i = 1; i <= 16; i++)
	{
		if (dead_or_live[i] == false) continue;
		for (int j = 0; j < 8; j++)
		{
			int nx = Fishes[i].pos.second + dx[Fishes[i].dir];
			int ny = Fishes[i].pos.first + dy[Fishes[i].dir];
			if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
			{
				Fishes[i].dir = (Fishes[i].dir + 1) % 9;
				if (Fishes[i].dir == 0) Fishes[i].dir++;
				continue;
			}
			//상어가 있을 때
			if (mp[ny][nx] == -1)
			{
				Fishes[i].dir = (Fishes[i].dir + 1) % 9;
				if (Fishes[i].dir == 0) Fishes[i].dir++;
				continue;
			}

			pii tmp = { ny,nx };
			swap_fish(mp, Fishes, tmp , Fishes[i].pos);
			break;
		}
	}
}

void simulation(vector<vector<int>> mp, vector<bool> dead_or_live, vector<Fish> Fishes, Shark shk, int sum)
{
	move_fish(mp, dead_or_live, Fishes);

	vector<pii> eat_list;
	int multiple = 1;
	while (1)
	{
		int nx = shk.pos.second + (dx[shk.dir] * multiple);
		int ny = shk.pos.first + (dy[shk.dir] * multiple);
		if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) break;
		if (mp[ny][nx] == 0) { multiple++; continue; }
		eat_list.push_back({ ny,nx });
		multiple++;
	}
	if (eat_list.size() == 0)
	{
		ans = max(ans, sum);
		return;
	}

	for (int i = 0; i < eat_list.size(); i++)
	{
		Shark new_shark;
		int y = eat_list[i].first; int x = eat_list[i].second;
		int num = mp[y][x];

		new_shark = { Fishes[num].dir, {y,x} };
		dead_or_live[num] = false;
		mp[y][x] = -1;
		mp[shk.pos.first][shk.pos.second] = 0;
		simulation(mp, dead_or_live, Fishes, new_shark, sum + num);
		mp[y][x] = num;
		mp[shk.pos.first][shk.pos.second] = -1;
		dead_or_live[num] = true;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<int>> mp(4, vector<int>(4, 0));
	vector<Fish> Fishes;
	vector<bool> dead_or_live(17, true);
	int num, dir;
	Fishes.resize(17);
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cin >> num >> dir;
			mp[i][j] = num;
			Fishes[num] = { dir, {i,j} };
		}
	}
	
	int sum = mp[0][0];
	int shark_dir = Fishes[mp[0][0]].dir;
	dead_or_live[mp[0][0]] = false;
	mp[0][0] = -1;

	Shark shk = { shark_dir, {0,0} };
	simulation(mp, dead_or_live, Fishes, shk, sum);
	cout << ans;
}

구현 문제는 항상 느끼는거지만 기능적인면을 코드 짤때는 어렵진 않은데, 초반에 자료를 어떤식으로 관리하고 구성할지가 제일 어려운 것 같다...

굳