백준 19236: 청소년 상어(C언어)

19236번: 청소년 상어

문제

아기 상어가 성장해 청소년 상어가 되었다.

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

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

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

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

 

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

 

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

 

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

 

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

 

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

 

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고,

1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

---

문제풀이

위의 내용을 정리해보면

1. a, b로 물고기 번호, 방향을 배열 4x4크기로 입력 받는다.

2. 입력 받은 내용을 바탕으로 물고기 구조체에 값을 입력한다.

3. 상어를 (0, 0)부터 배치하며 물고기를 먹는다.

4. 물고기가 이동할 수 있는 방향으로 낮은 순서의 물고기부터 차례대로 이동한다. (빈칸, 다른 물고기가 있는 칸만 가능)

5. 상어가 잡아먹은 물고기의 방향대로 칸수의 상관 없이 이동한다. (물고기가 있는 칸만 이동 가능)

6. (3, 4, 5)번을 상어가 이동 불가능한 상태가 될 때까지 반복.

 

정리한 내용을 바탕으로 1, 2번 먼저 수행을 해준다. 물고기는 1~16까지 이기 때문에 fish[17]의 0번 객체는 버린다.

마찬가지로 방향도 1~8까지라서 맨처음 0번 인덱스는 버린다.

최종 값은 전역변수로 설정하여 함수 안에서의 결과 값을 받아온다.

4x4 크기의 배열을 생성하며 물고기 번호, 방향(a, b) 값으로 받아오고 그 즉시 물고기 (x, y, 방향(dir))의 값에 담아준다.

(3, 4, 5)번의 내용을 한번에 처리해주기 위해 함수 shark_wave를 만들었고,

매개변수로 4x4배열, 물고기 객체, 상어 x(행)위치, 상어 y(열)위치, 최종 경우의 수마다의 합)을 설정해주었다.

#include<stdio.h>
// 물고기 1~16까지의 (x, y, 방향)을 담을 구조체 생성
typedef struct FISH {
	int x, y;
	int dir;
}FISH;
// 방향(이동x, 위, 왼쪽위, 왼쪽, 왼쪽아래, 아래, 오른쪽아래, 오른쪽, 오른쪽위)
int dx[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };

int answer; // 최종 값

// 상어가 물고기 먹기 -> 물고기 이동 -> 상어 이동을 한번에 처리해줄 함수(DFS방식)
void shark_wave(int arr[4][4], FISH fish[17], int shark_x, int shark_y, int sum){
}

int main() {
	int arr[4][4] = { 0 };
	FISH fish[17] = { 0 };
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b;
			scanf("%d %d", &a, &b);
			fish[a].x = i;
			fish[a].y = j;
			fish[a].dir = b;
			arr[i][j] = a;
		}
	}
	answer = 0;
	shark_wave(arr, fish, 0, 0, 0);
	printf("%d", answer);
	return 0;
}

 

 

원하는 결과 값이 여러가지의 경우의 수 중에서 가장 큰 값을 원하기 때문에 모든 경우의 수를 다 돌아봐야 한다.

따라서 DFS(깊이 우선 탐색) 방식을 선택하였고, 마지막 노드에 도달하게 되면 이전 단계로 돌아가야 하는데 배열 형태의 입력

값들을 되돌리기 위해 _temp를 붙혀서 똑같은 크기의 배열을 만들어 저장해주었다.

재귀호출을 통해서 여러가지의 경우의 수를 다 돌아보며 함수 안에서 먹은 물고기 값들을 sum에 더해주다가 answer값보다

sum이 큰 값이면 answer 값에 sum값을 넣어줌으로써 최대 크기 값을 찾아낸다.

최종코드

 

#include<stdio.h>
// 물고기 1~16까지의 (x, y, 방향)을 담을 구조체 생성
typedef struct FISH {
	int x, y;
	int dir;
}FISH;
// 방향(이동x, 위, 왼쪽위, 왼쪽, 왼쪽아래, 아래, 오른쪽아래, 오른쪽, 오른쪽위)
int dx[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };

int answer; // 최종 값

// 상어가 물고기 먹기 -> 물고기 이동 -> 상어 이동을 한번에 처리해줄 함수(DFS방식)
void shark_wave(int arr[4][4], FISH fish[17], int shark_x, int shark_y, int sum) {
	// DFS방식을 사용하기 때문에 이전 단계의 메모리를 저장할 공간을 만들어줌 _temp
	int arr_temp[4][4];
	FISH fish_temp[17];
	for (int i = 0; i < 17; i++) {
		fish_temp[i] = fish[i];
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			arr_temp[i][j] = arr[i][j];
		}
	}
	// 상어 물고기 먹기
	int shark_dir = fish_temp[arr_temp[shark_x][shark_y]].dir;
	sum += arr_temp[shark_x][shark_y];
	fish_temp[arr_temp[shark_x][shark_y]].x = -1;
	fish_temp[arr_temp[shark_x][shark_y]].y = -1;
	fish_temp[arr_temp[shark_x][shark_y]].dir = -1;
	arr_temp[shark_x][shark_y] = -1;
	if (answer < sum) {
		answer = sum;
	}
	// 물고기 이동
	for (int i = 1; i < 17; i++) {
		if (fish_temp[i].x == -1) { // 물고기가 이미 먹힌 경우 스킵
			continue;
		}
		int bx = fish_temp[i].x; // 이동 전 물고기 위치(before)
		int by = fish_temp[i].y;
		int bdir = fish_temp[i].dir;

		int ax = bx + dx[bdir]; // 이동 후 물고기 위치(after)
		int ay = by + dy[bdir];
		int adir = bdir;

		// 이동 불가능한 위치인지 체크
		while (ax < 0 || ax > 3 || ay < 0 || ay > 3 || (shark_x == ax && shark_y == ay)) {
			adir = (adir + 1) % 9;
			if (adir == 0) adir = 1;
			ax = bx + dx[adir];
			ay = by + dy[adir];
		}
		// 이동하려는 칸에 물고기가 있으면 물고기의 위치를 서로 바꿔줌
		if (arr_temp[ax][ay] != -1) {
			int temp = arr_temp[ax][ay];
			arr_temp[ax][ay] = i;
			arr_temp[bx][by] = temp;
			fish_temp[temp].x = bx;
			fish_temp[temp].y = by;
			fish_temp[i].x = ax;
			fish_temp[i].y = ay;
			fish_temp[i].dir = adir;
		}
		// 물고기가 없으면
		else {
			arr_temp[ax][ay] = i;
			arr_temp[bx][by] = -1;
			fish_temp[i].x = ax;
			fish_temp[i].y = ay;
			fish_temp[i].dir = adir;
		}
	}
	// 상어 이동
	// 상어가 이동할 수 있는 최소, 최대 칸수가 1~3 칸
	for (int i = 1; i < 4; i++) {
		int ax = shark_x + dx[shark_dir] * i;
		int ay = shark_y + dy[shark_dir] * i;

		// 상어가 격자 밖으로 나가는 경우 함수 종료
		if (ax < 0 || ax > 3 || ay < 0 || ay > 3) break;
		// 물고기가 있으면 재귀호출
		if (arr_temp[ax][ay] != -1) shark_wave(arr_temp, fish_temp, ax, ay, sum);
	}
}

int main() {
	int arr[4][4] = { 0 };
	FISH fish[17] = { 0 };
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b;
			scanf("%d %d", &a, &b);
			fish[a].x = i;
			fish[a].y = j;
			fish[a].dir = b;
			arr[i][j] = a;
		}
	}
	answer = 0;
	shark_wave(arr, fish, 0, 0, 0);
	printf("%d", answer);
	return 0;
}