청소년 상어 (feat. 백준, 19236번)

청소년 상어
https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/19236
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct Fish {
	int x, y, d;
};
int dx[8], dy[8];
int maps[4][4];
vector<int> results;
void move(int (*tmp)[4], map<int, Fish>& fish, int try_count) {
	for (auto iter = fish.begin(); iter != fish.end();) {
		if (try_count == 8) {
			try_count = 0, ++iter;
			continue;
		}
		auto& f = iter->second;
		auto nx = f.x + dx[f.d], ny = f.y + dy[f.d];
		if (0 <= nx && nx < 4 && 0 <= ny && ny < 4)
			if (tmp[nx][ny] == -1) {
				f.d = (f.d + 1) % 8;
				++try_count;
			}
			else {
				if (tmp[nx][ny] != 0) {
					auto& nd = tmp[nx][ny];
					fish[nd].x = f.x, fish[nd].y = f.y;
				}
				swap(tmp[f.x][f.y], tmp[nx][ny]), f.x = nx, f.y = ny;
				try_count = 0;
				++iter;
			}
		else
			f.d = (f.d + 1) % 8, ++try_count;
	}
}
void dfs(const int& x, const int& y, int result, int (*tmp)[4], map<int, Fish> fish) {
	int arr[4][4];
	memcpy(arr, tmp, sizeof(int) * 4 * 4);
	Fish shark = fish[arr[x][y]];
	result += arr[x][y], fish.erase(arr[x][y]), arr[x][y] = -1;
	move(arr, fish, 0);
	arr[x][y] = 0;

	while (true)
	{
		auto nx = shark.x + dx[shark.d], ny = shark.y + dy[shark.d];
		if (0 <= nx && nx < 4 && 0 <= ny && ny < 4) {
			shark.x = nx, shark.y = ny;
			if (arr[nx][ny] > 0)
				dfs(nx, ny, result, arr, fish);
		}
		else
			break;
	}

	results.push_back(result);
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = dx[1] = dx[7] = -1, dx[2] = dx[6] = 0, dx[3] = dx[4] = dx[5] = 1;
	dy[0] = dy[4] = 0, dy[1] = dy[2] = dy[3] = -1, dy[5] = dy[6] = dy[7] = 1;
	map<int, Fish> fish;
	for (int ix = 0, iy, n, d; ix < 4; ++ix)
		for (iy = 0; iy < 4; ++iy)
			cin >> n >> d, maps[ix][iy] = n, fish[n] = Fish{ ix, iy, d - 1 };
	dfs(0, 0, 0, maps, fish);
	cout << *max_element(results.begin(), results.end()) << endl;
	return 0;
}
// *&)*@*

1. 상어가 이동하는 경우, 만약 물고기가 없다면 바로 종료하지 않고 다음번으로 넘어가야 합니다.
2. 위의 경우가 종료되는 조건은 공간을 벗어난 곳으로 상어가 가려고 할때 입니다.
3. 해당 문제와 같이 여러 조건이 있고 그중 한 조건에 대해서 또 여러 조건이 있는 경우는 보통 재귀적으로 풀이가 가능합니다.
4. 단, 상태표시들(x,y에 존재하는 물고기 번호, 상어에게 잡아먹힌 물고기를 관리하는 탬플릿 등)도 재귀적으로 넘겨줘야 합니다. (전역으로 사용하거나 call by reference로 사용하게 되면 해당 조건이 끝난 이후에 다시 데이터를 복구해주어야 하는 복잡함이 발생하기 때문입니다.)