[백준] 19236 - 청소년 상어

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

19236번: 청소년 상어

 

정말 이런 빡 구현 문제를 풀 때마다 수명이 줄어지는 것이 느껴진다.

이런 문제는 디버깅도 매우 어렵고 조금만 실수해도 답이 확 틀어진다.

 

이 문제를 다시 돌이켜보면, 그렇게 큰 실수가 아니었음에도 다시 풀면 한 번에 맞출 자신이 없다.

꾸준히 구현 문제를 풀어서 실수를 줄여나가야겠다.

 

먼저 물고기의 상태를 나타내는 구조체를 하나 선언하였다.

좌표, 방향, 생존여부이다.

 

struct fish {
	int x;
    int y;
    int dir;
    bool on;
};

 

그리고 나는 배열을 복사하는 코드를 적기 싫어해서 벡터로 선언해 참조 형태로 전달하였다.

다음은 물고기가 움직이는 과정이다.

1. 1번 물고기부터, 16번 물고기까지 살아있을 때 진행한다.
2. 해당 물고기의 방향을 포함해 반시계 방향으로 돌아가며 가능한 경우를 찾는다.
3. 가능한 경우를 찾으면, 물고기를 스위칭해주고 break를 건다.

 

void fishMove(vector<fish>& f, vector<vector<int>>& map, pair<int, int> s) {

	for (int i = 1; i <= 16; i++) {
		if (!f[i].on) continue;

		for (int k = 0; k < 8; k++) {

			int nDir = f[i].dir + k;
			if (nDir > 8) nDir -= 8;
			int nx = f[i].x + dx[nDir];
			int ny = f[i].y + dy[nDir];


			if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && !(nx == s.first && ny == s.second)) {
				f[i].dir = nDir;

				int nowDir = f[i].dir;
				int nowX = f[i].x;
				int nowY = f[i].y;

				pair<int, int> coor = { f[i].x,f[i].y };
				f[i].x = nx, f[i].y = ny;
				f[map[nx][ny]].x = coor.first, f[map[nx][ny]].y = coor.second;

				int num = map[nx][ny];
				map[nx][ny] = i;
				map[coor.first][coor.second] = num;
				break;
			}
		}
	}
}

 

다음은 dfs 과정이다.

물고기를 움직이고 나서, 상어는 해당하는 줄(행, 열, 대각선)에 최대 3마리의 물고기 중에서 하나를 고를 수 있다.

이 과정을 백트래킹으로 해결하였다.

 

void go(vector<fish> f, pair<int, int> s, int sDir, vector<vector<int>> map, int cnt) { //cnt = 먹은 물고기 개수

	ans = max(ans, cnt);

	fishMove(f, map, s);

	//sharkMove start
	for (int i = 1; i <= 3; i++) {
		int nx = s.first + dx[sDir] * i;
		int ny = s.second + dy[sDir] * i;
		if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny]) {

			int fishNum = map[nx][ny];

			map[nx][ny] = 0;
			f[fishNum].on = false;

			go(f, { nx,ny }, f[fishNum].dir, map, cnt + fishNum);

			map[nx][ny] = fishNum;
			f[fishNum].on = true;
		}
	}
	//sharkMove end
}

 

다음은 전체 코드이다.

 

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

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 ans = 0;

struct fish {
	int x;
	int y;
	int dir;
	bool on;
};

void fishMove(vector<fish>& f, vector<vector<int>>& map, pair<int, int> s) {

	for (int i = 1; i <= 16; i++) {
		if (!f[i].on) continue;

		for (int k = 0; k < 8; k++) {

			int nDir = f[i].dir + k;
			if (nDir > 8) nDir -= 8;
			int nx = f[i].x + dx[nDir];
			int ny = f[i].y + dy[nDir];


			if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && !(nx == s.first && ny == s.second)) {
				f[i].dir = nDir;

				int nowDir = f[i].dir;
				int nowX = f[i].x;
				int nowY = f[i].y;

				pair<int, int> coor = { f[i].x,f[i].y };
				f[i].x = nx, f[i].y = ny;
				f[map[nx][ny]].x = coor.first, f[map[nx][ny]].y = coor.second;

				int num = map[nx][ny];
				map[nx][ny] = i;
				map[coor.first][coor.second] = num;
				break;
			}
		}
	}
}

void go(vector<fish> f, pair<int, int> s, int sDir, vector<vector<int>> map, int cnt) { //cnt = 먹은 물고기 개수

	ans = max(ans, cnt);

	fishMove(f, map, s);

	//sharkMove start
	for (int i = 1; i <= 3; i++) {
		int nx = s.first + dx[sDir] * i;
		int ny = s.second + dy[sDir] * i;
		if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny]) {

			int fishNum = map[nx][ny];

			map[nx][ny] = 0;
			f[fishNum].on = false;

			go(f, { nx,ny }, f[fishNum].dir, map, cnt + fishNum);

			map[nx][ny] = fishNum;
			f[fishNum].on = true;
		}
	}
	//sharkMove end
}

int main() {

	vector<fish> f(17);
	vector<vector<int>> map(4, vector<int>(4));
	pair<int, int> s = {};
	int sDir = 0;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int num, dir;
			cin >> num >> dir;
			fish a = { i,j,dir,true };
			f[num] = a;
			map[i][j] = num;
		}
	}

	int fNum = map[0][0];
	s = { 0,0 }, sDir = f[fNum].dir;
	f[fNum].on = false;
	map[0][0] = 0;

	go(f, s, sDir, map, fNum);

	cout << ans;
}

 

생각보다 그리 코드가 길지 않은데 실수가 잦은 문제였다.