[BOJ][삼성기출] 19236. 청소년 상어

문제 접근

1. 상어가 물고기를 먹는다.
2. 물고기는 번호가 작은 순서대로 차례로 움직인다.

   모든 물고기는 방향을 가지며, 한 칸을 움직일 수 있다.
   범위 내에서(4x4), 이동하고자 하는 위치가 빈 공간이거나 다른 물고기가 있을 경우 이동 가능하다.
   다른 물고기가 있을 경우 그 물고기와 위치를 바꾼다.
   물고기는 처음에 입력 받은 방향으로 이동을 시도한다.
   만일 이동할 수 없다면 반시계 방향으로 45도씩 회전하며 이동 가능한 방향을 찾는다.
   이동 가능한 방향을 찾을 경우, 물고기의 방향을 바뀐 방향으로 다시 세팅해 주어야 한다.

3. 상어가 움직인다.

   상어는 먹은 물고기의 방향을 가지며, 해당 방향으로 몇 칸이든 움직일 수 있다.
   상어가 물고기를 먹었을 때, 물고기를 죽이고 상어를 물고기가 있는 곳으로 이동시킨 후 다음 dfs함수를 호출했다.
   포인트는 앞서 호출한 dfs함수의 수행이 끝나고 난 뒤, 먹은 물고기와 상어의 위치를 복구시키는 것이다.

4. 완전 탐색 문제이다.
   map과 Fish의 sync를 맞추는 게 중요하다.
   두 개의 자료구조를 두어 탐색마다 sync를 맞추는 유형을 연습하기 좋았다.
   backtracing 으로 DFS 문제를 푸는 패턴을 익힐 수 있었다.

풀이

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct fish {
	int x;
	int y;
	int dir;
	bool live;
} fish;

int map[4][4];
fish Fish[17];
int rst;
int dx[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

void input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int num, dir;
			cin >> num >> dir;
			Fish[num] = { i, j, dir, true };
			map[i][j] = num;
		}
	}
	rst = 0;
}

void copy_state(int dst_map[][4], int src_map[][4], fish dst_fish[], fish src_fish[]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			dst_map[i][j] = src_map[i][j];
		}
	}
	for (int i = 1; i <= 16; i++) {
		dst_fish[i] = src_fish[i];
	}
}

int is_range(int x, int y) {
	if (x >= 0 && x < 4 && y >= 0 && y < 4) return true;
	return false;
}

void move_fish() {
	for (int num = 1; num <= 16; num++) {
		if (!Fish[num].live) continue;
		int x = Fish[num].x;
		int y = Fish[num].y;
		int dir = Fish[num].dir;
		int nx, ny, ndir;
		bool flag = false;
		for (int i = 0; i <= 7; i++) {
			ndir = dir + i;
			if (ndir > 8) ndir = ndir - 8;
			nx = x + dx[ndir];
			ny = y + dy[ndir];
			if (!is_range(nx, ny) || map[nx][ny] == -1) continue;
			flag = true;
			break;
		}
		if (!flag) continue; // no possible dir to change
		Fish[num].dir = ndir; // change dir of fish
		if (map[nx][ny] == 0) { // empty space
			map[x][y] = 0;
			map[nx][ny] = num;
			Fish[num].x = nx;
			Fish[num].y = ny;
		}
		else { // swap fish
			int target = map[nx][ny];
			map[nx][ny] = num; // change info on map
			map[x][y] = target;
			Fish[num].x = nx; // change info on fish structure
			Fish[num].y = ny;
			Fish[target].x = x;
			Fish[target].y = y;
		}
	}
}

void dfs(int x, int y, int dir, int cnt) {
	rst = max(cnt, rst);
	int c_map[4][4];
	fish c_Fish[17];
	copy_state(c_map, map, c_Fish, Fish); // save

	move_fish(); // 1. move fish

	for (int i = 1; i <= 3; i++) { // 2. move shark
		int nx = x + dx[dir] * i;
		int ny = y + dy[dir] * i;
		if (!is_range(nx, ny) || map[nx][ny] == 0) continue;
		int f_num = map[nx][ny];
		int ndir = Fish[f_num].dir;

		Fish[f_num].live = false; // eat fish & move shark
		map[x][y] = 0;
		map[nx][ny] = -1;

		dfs(nx, ny, ndir, cnt + f_num);
	
		Fish[f_num].live = true; // restroe fish and shark
		map[x][y] = -1;
		map[nx][ny] = f_num;
	}
	copy_state(map, c_map, Fish, c_Fish); // restore
}

void solve() {
	int f_num = map[0][0];
	Fish[f_num].live = false;
	map[0][0] = -1;
	dfs(0, 0, Fish[f_num].dir, f_num);
}

int main() {
	input();
	solve();
	cout << rst << endl;
}

• 방향이 1부터 8까지 주어졌는데 괜히 0부터 7까지로 바꿔 푸느라 처음에 헷갈리고 말았다.
  그냥 주어진 숫자를 최대한 활용할 수 있도록 문제를 구성하는 게 '디버깅' 시 편하다!
• 물고기가 방향을 바꿀 경우, 바뀐 방향을 업데이트 해줘야 하는데 이 부분을 코드만 보고 캐치하지 못하다 디버깅 화면을 보며 문득 깨달았다. 이런 사소한 포인트를 놓치지 말 것.