백준 - 청소년 상어 (19236번)

백준 - 청소년 상어 (19236번)

문제 설명이 쓸데없이 복잡해서 몇 번 읽어봤다.

풀이의 핵심은 dfs + 시뮬레이션 정도이고, 0ms만에 해결하려면 물고기, 상어를 가지고 있는 Map 뿐만 아니라 물고기들의 Index를 순서대로 가지고 있는 배열을 따로 관리해야 하는 것 같다. (물고기가 움직이는 것은 물고기 Index 순서대로이기 때문에)

상어가 움직일 수 있는 위치가 1가지 경우가 아니라 여러 경우가 나올 수 있으며, 그 중 상어가 움직임에 따라서 잡아먹은 물고기의 Index의 최대 값을 구하는 문제이기 때문에 dfs를 이용해서 풀어야 한다.
상어와 물고기가 움직일 수 있는 경우가 다르기 때문에 이를 분류해주고, 상어가 움직일 때마다 Map, Fish_List를 업데이트 해주면서 DFS를 해주면 된다.

코드는 아래와 같다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct __fish_info {
	int idx;
	int dir;
	int row;
	int col;
	int alive;
}fish_info;

typedef struct __shark_info {
	int row;
	int col;
	int dir;
}shark_info;

int init_map[4][4];
shark_info init_shark;
fish_info init_fish_list[17];

int rowDir[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int colDir[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };

void init_shark_info()
{
	int idx = init_map[0][0];
	init_shark.row = init_fish_list[idx].row;
	init_shark.col = init_fish_list[idx].col;
	init_shark.dir = init_fish_list[idx].dir;

	init_fish_list[idx].alive = false;

	init_map[0][0] = -1;
}

const inline bool is_fish_move_safe(const int map[4][4], int row, int col)
{
	if (row < 0 || row > 3 || col < 0 || col > 3)
		return false;

	if (map[row][col] == -1)
		return false;

	return true;
}

void move_fish(fish_info fish_list[17], int map[4][4]) {
	for (int i = 1; i <= 16; i++) {
		if (!fish_list[i].alive)
			continue;

		int row = fish_list[i].row;
		int col = fish_list[i].col;
		int dir = fish_list[i].dir;
		int cnt = 0;
		while (1) {
			int nrow = row + rowDir[dir];
			int ncol = col + colDir[dir];
			cnt++;
			if (is_fish_move_safe(map, nrow, ncol)) {
				int nidx = map[nrow][ncol];

				map[row][col] = nidx;
				map[nrow][ncol] = i;
				fish_list[i].row = nrow;
				fish_list[i].col = ncol;
				fish_list[nidx].row = row;
				fish_list[nidx].col = col;
				fish_list[i].dir = dir;
				break;
			}
			if (cnt > 8)
				break;
			dir = (dir + 1) % 8;
		}
	}
}

const inline bool is_shark_move_safe(const int map[4][4], int row, int col)
{
	if (row < 0 || col < 0 || row > 3 || col > 3)
		return false;

	if (map[row][col] == 0)
		return false;

	return true;
}

int eat_fish(shark_info &shark, fish_info fish_list[17], int map[4][4], int row, int col)
{
	int idx = map[row][col];

	// 상어가 지나간 자리는 빈 칸으로 설정
	map[shark.row][shark.col] = 0;

	// 상어의 위치 업데이트
	shark.row = fish_list[idx].row;
	shark.col = fish_list[idx].col;
	shark.dir = fish_list[idx].dir;

	// fish_list 중 fish가 죽은 것 업데이트
	fish_list[idx].alive = false;

	// 해당 위치에 상어가 있다고 업데이트
	map[row][col] = -1;

	return idx;
}

int move_shark(shark_info& shark, fish_info fish_list[17], int map[4][4], int len)
{
	int nrow = shark.row + len * rowDir[shark.dir];
	int ncol = shark.col + len * colDir[shark.dir];
	if (!is_shark_move_safe(map, nrow, ncol))
		return 0;

	return eat_fish(shark, fish_list, map, nrow, ncol);
}

int solve(shark_info __shark, fish_info __fish_list[17], int __map[4][4], int len, int depth)
{
	shark_info shark = __shark;
	fish_info fish_list[17];
	int map[4][4];
	for (int i = 1; i <= 16; i++) 
		fish_list[i] = __fish_list[i];
	for (int i = 0; i < 4; i++) 
		for (int j = 0; j < 4; j++) 
			map[i][j] = __map[i][j];
		
	move_fish(fish_list, map);
	int result = move_shark(shark, fish_list, map, len);

	if (result > 0) {
		int next_result = 0;
		for (int i = 1; i < 4; i++) 
			next_result = max(solve(shark, fish_list, map, i, depth + 1), next_result);
		result += next_result;
	}
	
	return result;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	fish_info fish;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {		
			cin >> fish.idx >> fish.dir;
			fish.row = i; fish.col = j; fish.alive = true; fish.dir--;
			init_map[i][j] = fish.idx;
			init_fish_list[fish.idx] = fish;
		}
	}

	int init_val = init_map[0][0];
	init_shark_info();
	int result = 0;
	for (int i = 1; i < 4; i++) {
		int tmp =  solve(init_shark, init_fish_list, init_map, i, 0);
		result = max(tmp, result);
	}

	result += init_val;
	cout << result << "\n";

	return 0;
}