[BOJ 19236] 청소년 상어 (C++)

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

19236번: 청소년 상어

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

int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };

struct fish {
	int num;
	int pos;
};

struct info {
	int shark_x, shark_y;
	vector<vector<fish> > graph;
	vector<pair<int, int> > v;
	int cnt;
};

void moveFish(vector<vector<fish> >& graph, vector<pair<int, int>>& v) {
	int x, y, pos, cnt;
	for (int i = 1; i <= 16; i++) {
		if (v[i].first == -1)	//탐색x 
			continue;
		x = v[i].first;
		y = v[i].second;
		pos = graph[x][y].pos;
		cnt = 8;
		while (cnt--) {
			int nx = x + dx[pos];
			int ny = y + dy[pos];
			if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
				if (graph[nx][ny].num == 0) {		//빈칸
					v[i].first = nx;
					v[i].second = ny;
					graph[nx][ny].num = i;
					graph[nx][ny].pos = pos;
					graph[x][y].num = 0;
					break;
				}
				else if (graph[nx][ny].num >= 1 && graph[nx][ny].num <= 16) {
					int temp_num = graph[nx][ny].num;
					int temp_pos = graph[nx][ny].pos;
					v[i].first = nx;
					v[i].second = ny;
					v[temp_num].first = x;
					v[temp_num].second = y;
					graph[nx][ny].num = i;
					graph[nx][ny].pos = pos;
					graph[x][y].num = temp_num;
					graph[x][y].pos = temp_pos;
					break;
				}
			}
			pos = (pos + 1) % 8;
		}
	}
}

int main() {
	vector<vector<fish> > graph(4);
	vector<pair<int, int> > v(17);
	int a, b;
	int ans = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> a >> b;
			graph[i].push_back({ a,b-1 });
			v[a] = { i,j };
		}
	}
	//shark 이동
	int prev_pos = graph[0][0].pos;	
	int prev_num = graph[0][0].num;
	v[prev_num] = { -1,-1 };	//(0,0) 자리에 위치한 
	graph[0][0] = { 17,prev_pos }; //17: 상어
	queue<info> q;
	q.push({ 0,0,graph,v,prev_num });
	while (!q.empty()) {
		int possible = 0;
		info i = q.front();
		q.pop();
		//goal check
		int next_x = i.shark_x + dx[i.graph[i.shark_x][i.shark_y].pos];
		int next_y = i.shark_y + dy[i.graph[i.shark_x][i.shark_y].pos];
		if (next_x < 0 || next_x >= 4 || next_y < 0 || next_y >= 4) {
			ans = max(ans, i.cnt);
			continue;
		}
		//물고기 이동
		moveFish(i.graph, i.v);
		//가능한 쪽으로 상어 이동하여 큐에 넣기
		int shark_pos = i.graph[i.shark_x][i.shark_y].pos;
		int new_shark_x = i.shark_x + dx[shark_pos];
		int new_shark_y = i.shark_y + dy[shark_pos];
		while (new_shark_x >= 0 && new_shark_x < 4 && new_shark_y >= 0 && new_shark_y < 4) {
			if (i.graph[new_shark_x][new_shark_y].num != 0) {
				vector<vector<fish> > new_graph = i.graph;
				vector<pair<int, int> > nv = i.v;
				new_graph[i.shark_x][i.shark_y].num = 0;
				int prey = new_graph[new_shark_x][new_shark_y].num;
				nv[prey] = { -1,-1 };
				new_graph[new_shark_x][new_shark_y].num = 17;
				q.push({ new_shark_x, new_shark_y, new_graph, nv, i.cnt + prey });
				possible++;
			}
			new_shark_x += dx[shark_pos];
			new_shark_y += dy[shark_pos];
		}
		if (possible == 0) {					//방향으로 모두 빈칸일때, 집에 가므로 ans 계산
			ans = max(ans, i.cnt);
		}
	}
	cout << ans << "\n";
	return 0;
}

 

시뮬레이션+백트래킹(DFS) 문제였다.

 

나는 큐를 이용해서 거의 BFS 방식으로 풀었는데, 깔끔하게 풀리지 않았다. 예외처리도 곳곳에 해줘야했다.

DFS를 사용해서 완전탐색, 백트래킹을 해주는게 출제자의 의도같다.

 

다른 분의 코드를 보니(https://yjyoon-dev.github.io/boj/2020/11/17/boj-19236/)

solve(y,x): (y,x) 자리 물고기를 먹고 난 이후 누적합 반환한다.

상어가 이동한 상태=>물고기 움직임=>다음 상어의 움직임 재귀로 호출해준다.