[Algorithm][C++] BOJ 19236 청소년 상어

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

19236번: 청소년 상어

 

풀이 핵심

1. Bruth Force + 시뮬레이션 / 구현 문제

 

2. shark라는 struct를 만들어 문제를 해결한다. shark struct는 다음과 같은 변수, 함수로 구성된다.

• 현재 상어의 위치 (R, C), 방향 (D), 먹은 물고기 번호의 합 (cnt)
• 물고기의 ID를 저장하는 map[4][4] 배열
• 물고기의 위치, 방향, ID를 저장하는 fish 배열 (배열의 인덱스가 ID가 되도록 한다, 배열의 인덱스가 ID 임에도 추가적으로 id 요소를 가지고 있는 이유는 물고기가 죽었는지를 id == 0 으로 판단할 것이기 때문이다.)
• void eat (int y, int x) 함수는 map의 위치를 입력하면 상어의 방향을 그 물고기의 방향으로 바꾸고 cnt에 그 물고기의 ID를 더한다. 그리고 물고기의 ID를 0으로 만들어 map에 표시한다. 상어의 현재 위치를 입력 값으로 변경한다.
• void move_fish() 함수는 1번 부터 16번까지의 물고기를 순차적으로 이동시킨다. 만일 물고기의 id가 0이면 죽었다는 뜻으로 판단하고 다음 물고기를 이동시킨다. 물고기가 이동가능 한 위치가 0인지 꼭 확인해 줘야 한다

 

3. dfs 함수를 통해 완전 탐색한다.

• 물고기를 이동시킨다.
• 상어가 이동할 방향으로 최대 이동 가능한 경우는 3가지 이므로 for 문을 3번 반복한다. 만약 for 문을 모두 돌고 한번도 dfs에 다시 들어가지 못하면 상어가 이동가능한 곳이 없다고 판단해 현재의 cnt를 ans와 비교한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int ans;
const int dr[] = { -1,-1,0,1,1,1,0,-1 };
const int dc[] = { 0,-1,-1,-1,0,1,1,1 };

struct SHARK {
	int R, C, D, cnt; // 현재 상어 위치, 방향, 물고기 먹은 번호 합
	int map[4][4]; // 물고기 ID가 저장된 배열

	struct FISH { int r, c, d, id; };
	FISH fish[16 + 1]; // 물고기 정보 (배열 인덱스가 물고기의 ID)

	void eat(int y, int x) { // 상어 이동 (물고기 먹음)
		cnt += map[y][x];
		D = fish[map[y][x]].d;
		fish[map[y][x]].id = 0;
		map[y][x] = 0;
		R = y, C = x;
	}

	void move_fish() { // 물고기 이동
		for (int i = 1; i <= 16; i++) {
			if (fish[i].id == 0) continue;
			FISH cur = fish[i];
			int nr = cur.r + dr[cur.d];
			int nc = cur.c + dc[cur.d];
			if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 || (nr == R && nc == C)) {
				int j;
				for (j = 0; j < 7; j++) {
					cur.d = (cur.d + 1) % 8;
					nr = cur.r + dr[cur.d];
					nc = cur.c + dc[cur.d];
					if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 \
                    || (nr == R && nc == C)) {
						continue;
					}
					break;
				}
				if (j == 7) continue;
			}
			FISH next{ 0, };
			if (map[nr][nc] != 0) {
				next = fish[map[nr][nc]];
			}
			map[nr][nc] = cur.id;
			map[cur.r][cur.c] = next.id;

			fish[i].r = nr, fish[i].c = nc, fish[i].d = cur.d;
			fish[next.id].r = cur.r, fish[next.id].c = cur.c;
		}
	}
};

void dfs(SHARK cur) {
	cur.move_fish(); // 물고기 이동
	int check = 0; // 상어의 이동 불가 확인용
	int nr = cur.R, nc = cur.C;
	for (int i = 0; i < 3; i++) {
		nr += dr[cur.D];
		nc += dc[cur.D];
		if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 || cur.map[nr][nc] == 0) continue;
		SHARK next = cur;
		next.eat(nr, nc);
		dfs(next);
		++check;
	}
	if (check == 0) { // 상어 더이상 이동 불가
		if (cur.cnt > ans) ans = cur.cnt;
		return;
	}
}

int main() {
	SHARK shark;
	shark.cnt = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int id, d;
			scanf("%d %d", &id, &d);
			--d; // 방향 배열 dr, dc의 인덱스는 0부터 시작하므로
			shark.map[i][j] = id;
			shark.fish[id] = { i,j,d,id };
		}
	}
	shark.eat(0, 0); // 상어의 시작 위치
	dfs(shark); // Bruth Force
	printf("%d", ans);
	return 0;
}

 

오랜만에 구글링(다른 풀이 참고) 없이 혼자만의 힘으로 문제를 잘 풀었다는 생각이 들었다 :)