[백준 19236] 청소년 상어

문제 링크 : 19236번: 청소년 상어 (acmicpc.net)

19236번: 청소년 상어

 

완전 탐색을 이용한 구현 문제이다.

문제 설명에 앞서 클래스 및 선언한 배열 및 상수에 대한 설명을 하려고 한다.

 

※ class Fish

 

Fish 라는 클래스를 선언하였고 아래코드와 같이 구현하였다.

class Fish {
public:
	bool live;
	int x, y, direction;
	Fish() {}
	Fish(int x, int y, int direction, bool live) {
		this->x = x;
		this->y = y;
		this->direction = direction;
		this->live = live;
	}

	bool check_go(int shark_x, int shark_y) {
		int fish_x = x, fish_y = y;
		int fish_direction = direction;

		fish_x += dx[fish_direction];
		fish_y += dy[fish_direction];
		return (is_in(fish_x, fish_y) && !(fish_x == shark_x && fish_y == shark_y));
	}

	void rotate() {
		direction += 1;
		if (direction == 9)
			direction = 1;
	}

	void go() {
		x += dx[direction];
		y += dy[direction];
	}
};

 

• bool live : i 번째 물고기가 살았는지 죽었는지를 판단하기 위한 변수이다. 
• check_go(int shark_x, int shark_y) : 매개변수로 shark의 위치를 받아와서 i 번째 물고기가 다음으로 이동할 때 영역 안에 존재하면서 상어의 위치와 겹치지 않을 경우 true, 그 외에 false 를 반환하는 함수이다.
• rotate() : direction 값을 1 증가하여 i 번째 물고기가 반시계 방향으로 45 도 회전하도록 하는 함수이다.
• go() : i 번째 물고기가 direction 방향으로 한 칸 이동하는 함수이다.

 

※ int dx[9], dy[9]

 

방향을 결정하도록 하는 배열을 다음과 같이 선언하였다.

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

 

인덱스를 1 부터 8 까지 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 에 대한 방향을 갖도록 설정하였다.

예를 들어서 인덱스가 3일 경우 ←, 7일 경우 → 이다.

 

※ Fish fish[17]

 

총 16 개의 물고기의 정보를 정하기 위해 Fish 클래스 타입의 배열 fish[17] 을 선언하였다.

예를 들어서 3 번째 물고기가 (1, 2) 위치에 ↓ 방향을 가르킬 경우 다음과 같이 설정할 수 있다.

fish[3].x = 1, fish[3].y = 2;	// 3 번째 물고기의 위치 : (1, 2)
fish[3].direction = 5;			// 3 번째 물고기가 가르키는 방향 : ↓
fish[3].live = true				// 3 번째 물고기의 생존 여부 : o

 

※ int info[4][4] / const int SHARK = 100, BLANK = 0

 

4 x 4 격자에 물고기가 놓였는지 상어가 놓였는지 아무것도 놓이지 않았는지에 대해 확인하기 위한 배열을 선언하였다.

그리고 격자 위에 물고기(1 ~ 16) 만 존재하는것이 아니라 상어가 존재할 수 있고 둘 다 존재하지 않을 수 있다.

예를 들어 (2, 3) 위치에 7 번 물고기가 있고 (0, 0) 위치에 상어가 있고 (1, 1) 위치에 아무것도 존재하지 않을 경우 다음과 같이 info 배열에 해당 정보를 저장할 수 있다.

info[2][3] = 7;		// (2, 3) 위치에 7 번 물고기가 존재
info[0][0] = SHARK;	// (0, 0) 위치에 상어가 존재
info[1][1] = BLANK;	// (1, 1) 위치에 아무것도 존재 x

 

문제 접근 방법

 

① 처음에 상어는 (0, 0) 위치에 해당하는 물고기를 잡아먹는다.

상어가 물고기를 잡아먹으면 상어는 잡아먹힌 물고기가 가르키는 방향을 그대로 따라하게 된다.

이에 대한 처리는 다음과 같이 하였다.

void shark_eat_fish(int die_fish, int shark_x, int shark_y)
{
	fish[die_fish].live = false;
	info[shark_x][shark_y] = SHARK;
}

void solution()
{
	int die_fish = info[0][0];

	shark_eat_fish(die_fish, 0, 0);
	cout << die_fish + dfs(fish[die_fish].x, fish[die_fish].y, fish[die_fish].direction);
}

 

die_fish 는 (0, 0) 에 죽은 물고기의 번호를 나타낸다.

shark_eat_fish 함수를 통해 죽은 물고기의 live 를 false 로 갱신하고 해당 위치에 SHARK 가 배치하도록 하였다.

현재 죽은 물고기의 번호 + dfs( ... ) 값은 상어가 먹을 수 있는 물고기 번호의 합의 최댓값이며 dfs( ... ) 함수가 결국 상어가 (0, 0) 위치에서 시작하여 얻어낼 수 있는 최댓값이 된다.

 

② 1 번 물고기부터 16 번 물고기까지 살아있는 물고기들에 대해서 이동하는 작업이 이루어져야 한다.

문제에서 주어진 조건을 일단 살펴보도록 하자.

 

1. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 
2. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
3. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다.
4. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

 

1 번 조건 :  물고기가 다음 칸으로 이동할 수 있는 무언가의 함수가 정의가 되어야 한다.

근데 이 함수는 클래스를 설명하면서 자연스럽게 설명한 부분이다.

bool check_go(int shark_x, int shark_y) {
	int fish_x = x, fish_y = y;
	int fish_direction = direction;

	fish_x += dx[fish_direction];
	fish_y += dy[fish_direction];
	return (is_in(fish_x, fish_y) && !(fish_x == shark_x && fish_y == shark_y));
}

 

is_in 함수를 통해 격자 내에 존재하며 상어의 위치와 동일하지 않을 경우 true 를 반환하여 다음 칸으로 이동할 수 있는지 여부를 확인할 수 있도록 하였다.

 

2 번 조건 :  45 도 반시계 방향으로 회전하는 함수는 rotate() 함수를 통해 이루어진다.

 

3 번 조건 :  check_go 함수를 통해 이동할 수 있는 경우 true 가 반환되어 해당하는 칸으로 이동하도록 처리해준다.

 

4 번 조건 : 다음 칸으로 이동할 경우 서로의 위치가 변경되도록 처리한다.

 

위 조건들을 고려하여 다음과 같이 코드를 작성하였다.

for (int i = 1; i <= 16; i++) {
	if (fish[i].live) {
		before_x = fish[i].x, before_y = fish[i].y;
		while (!fish[i].check_go(shark_x, shark_y)) {
			fish[i].rotate();
		}
		fish[i].go();
		next_fish = info[fish[i].x][fish[i].y];
		swap(info[before_x][before_y], info[fish[i].x][fish[i].y]);
		fish[next_fish].x = before_x, fish[next_fish].y = before_y;
	}
}

 

우선 i = 1, 2, ..., 16 순으로 작은 물고기 순으로 처리가 가능하도록 하였다.

i 번째 물고기가 생존할 경우 before_x, before_y 변수를 통해 현재 i 번째 물고기의 위치를 담아준다.

그 이유는 4 번 조건에서 서로의 위치가 변경되도록 처리하기 위해서 before_x, before_y 정보가 필요하다.

while 루프를 통해 이동이 불가능할 경우 반시계 방향으로 45도 회전하며 이동 가능할 때 까지를 반복한다.

이동 가능하게 될 경우 i 번째 물고기를 이동시킨 후, 이동한 위치의 물고기와 i 번째 물고기의 정보를 교환하여 4 번 조건에 대한 처리가 가능하게 된다.

 

③ 상어가 가르키는 방향으로 한 칸씩 이동하면서 해당 위치에 물고기가 놓여질 경우 물고기를 잡아먹고 ② 번 작업을 반복하도록 한다.

이때, 해당 위치에 대해서 모든 작업이 종료될 경우 그 다음 위치로 이동하여 물고기가 또 놓여질 경우 똑같이 ② 번 작업을 수행하도록 한다.

 

즉, 모든 경우를 탐색하여 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구할 수 있다.

그렇다면 재귀적으로 작업이 수행되기 전에 현재 정보를 유지하기 위한 임시 배열이 필요하다.

따라서 다음과 같이 임시 배열을 선언하였다.

int dfs(int shark_x, int shark_y, int shark_direction)
{
	int ret = 0;
	int before_x, before_y, die_fish, next_fish;
	int tmp_info[4][4];
	Fish tmp_fish[17];

	... (②)

	info[shark_x][shark_y] = BLANK;
	while (is_in((shark_x = shark_x + dx[shark_direction]),
		(shark_y = shark_y + dy[shark_direction]))) {
		if (info[shark_x][shark_y]) {
			copy(tmp_info, info, tmp_fish, fish);
			die_fish = info[shark_x][shark_y];
			shark_eat_fish(die_fish, shark_x, shark_y);
			ret = max(ret, die_fish + dfs(shark_x, shark_y, fish[die_fish].direction));
			copy(info, tmp_info, fish, tmp_fish);
		}
	}

	return ret;
}

 

info, fish 배열을 저장해두기 위해 tmp_info, tmp_fish 배열을 선언하였다.

우선 상어는 현재 위치에서 다음 위치로 이동하기 때문에 현재 위치를 BLANK 처리하였다.

그렇게 상어가 격자 내에서 이동하면서 물고기를 발견하게 될 경우 info, fish 에 대한 정보를 유지하도록 하고  ① 에서 설명한 방법과 동일하게 처리하면서 max 값을 갱신하여 리턴해주면 된다.

 

 

※ 풀이 코드

 

#include <iostream>

using namespace std;

bool is_in(int x, int y);
int dx[9] = { 0, -1,-1,0,1,1,1,0,-1 };
int dy[9] = { 0, 0,-1,-1,-1,0,1,1,1 };

class Fish {
public:
	bool live;
	int x, y, direction;
	Fish() {}
	Fish(int x, int y, int direction, bool live) {
		this->x = x;
		this->y = y;
		this->direction = direction;
		this->live = live;
	}

	bool check_go(int shark_x, int shark_y) {
		int fish_x = x, fish_y = y;
		int fish_direction = direction;

		fish_x += dx[fish_direction];
		fish_y += dy[fish_direction];
		return (is_in(fish_x, fish_y) && !(fish_x == shark_x && fish_y == shark_y));
	}

	void rotate() {
		direction += 1;
		if (direction == 9)
			direction = 1;
	}

	void go() {
		x += dx[direction];
		y += dy[direction];
	}
};

int info[4][4];
Fish fish[17];

const int BLANK = 0, SHARK = 100;

void input()
{
	int number, direction;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> number >> direction;
			info[i][j] = number;
			fish[number].x = i, fish[number].y = j;
			fish[number].direction = direction, fish[number].live = true;
		}
	}
}

int max(int x, int y)
{
	return (x > y ? x : y);
}

bool is_in(int x, int y) 
{
	return (x >= 0 && x <= 3 && y >= 0 && y <= 3);
}

void shark_eat_fish(int die_fish, int shark_x, int shark_y)
{
	fish[die_fish].live = false;
	info[shark_x][shark_y] = SHARK;
}

void fish_rollback(int live_fish, int fish_x, int fish_y)
{
	fish[live_fish].live = true;
	info[fish_x][fish_y] = live_fish;
}

void copy(int dst1[][4], int src1[][4], Fish dst2[], Fish src2[])
{
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			dst1[i][j] = src1[i][j];
	for (int i = 1; i <= 16; i++)
		dst2[i] = src2[i];
}

int dfs(int shark_x, int shark_y, int shark_direction)
{
	int ret = 0;
	int before_x, before_y, die_fish, next_fish;
	int tmp_info[4][4];
	Fish tmp_fish[17];

	for (int i = 1; i <= 16; i++) {
		if (fish[i].live) {
			before_x = fish[i].x, before_y = fish[i].y;
			while (!fish[i].check_go(shark_x, shark_y)) {
				fish[i].rotate();
			}
			fish[i].go();
			next_fish = info[fish[i].x][fish[i].y];
			swap(info[before_x][before_y], info[fish[i].x][fish[i].y]);
			fish[next_fish].x = before_x, fish[next_fish].y = before_y;
		}
	}

	info[shark_x][shark_y] = BLANK;
	while (is_in((shark_x = shark_x + dx[shark_direction]),
		(shark_y = shark_y + dy[shark_direction]))) {
		if (info[shark_x][shark_y]) {
			copy(tmp_info, info, tmp_fish, fish);
			die_fish = info[shark_x][shark_y];
			shark_eat_fish(die_fish, shark_x, shark_y);
			ret = max(ret, die_fish + dfs(shark_x, shark_y, fish[die_fish].direction));
			copy(info, tmp_info, fish, tmp_fish);
		}
	}

	return ret;
}

void solution()
{
	int die_fish = info[0][0];

	shark_eat_fish(die_fish, 0, 0);
	cout << die_fish + dfs(fish[die_fish].x, fish[die_fish].y, fish[die_fish].direction);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	input();
	solution();

	return 0;
}