[G2] 19236번 청소년 상어 C++ 백트래킹, 시뮬레이션, 구현, 재귀

리뷰

 

문제 이해에도 시간이 많이 걸리고 구현과 시뮬레이션 디버깅에도 다소 시간이 걸렸으나 한번에 풀긴 했다.

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

 

전역 변수

• dx, dy : 8방향 탐색을 위한 방향 배열
• v : 이미 잡아먹힌 물고기를 방문처리 하기 위한 배열
• max_val : 잡아먹은 물고기의 번호 최대값을 저장하기 위한 변수
• sdir : 최초에 잡아먹은 물고기가 갖고 있던 방향 정보를 저장하기 위한 변수
• Fish : 물고기의 위치와 진행 방향을 저장하기 위한 구조체
• fishes : 초기 물고기들의 위치와 방향 정보를 저장할 Fish타입 벡터
• lst : 초기 맵에 존재하는 물고기 번호를 저장하기 위한 4 * 4크기의 정수형 벡터

 

함수

1. input

void input()

 

4 * 4사이즈의 맵 정보를 입력 받고 물고기의 초기 위치와 방향 정보를 초기화 하는 함수

1. 물고기의 방향 정보가 1-based-indexing으로 주어지므로 해당 인덱스만 1감소시켜 주었다.

 

2. init

void init()

 

시뮬레이션 전에 초기값 세팅을 위한 함수

1. max_val을 초기 좌표 0, 0 위치의 물고기 번호로 초기화 해준다.
2. sdir을 초기 좌표 물고기가 갖고 있던 방향 정보로 초기화 해준다.
3. 초기 좌표 물고기는 잡아먹힌 상태이므로 v배열에 방문처리를 해주었다.
4. 초기 좌표에는 상어가 위치하므로 lst벡터의 초기 위치를 17로 변경해 주었다.

 

3. bt

void bt(int x, int y, int dir, int val, vector<vector<int>> map, vector<Fish> cur)

 

완전 탐색을 통해 상어가 갈 수 있는 위치를 시뮬레이션 하는 함수

1. x, y, dir : 현재 상어의 위치와 방향 정보를 매개변수로 전달한다.
2. val : 현재까지 상어가 먹은 물고기들의 번호 합을 매개변수로 전달한다.
3. map : 현재 재귀 단계에서의 맵 정보를 매개변수로 전달한다.
4. cur : 현재 물고기의 위치와 방향 상태 정보를 매개변수로 전달한다.
5. 이전 재귀단계에서의 물고기 정보를 새로운 벡터 temp에 깊은 복사를 해준다.
6. 1 ~ 16번의 물고기를 순회하며 방문처리 되지 않은 물고기들의 이동을 진행한다.
7. 8방향을 탐색할때 현재 방향 + i를 8로 나눈 값을 탐색해 주어 현재 물고기가 바라보는 방향부터 탐색해 준다.
8. 만약 진행방향이 현재 맵상에서 17이라면 상어이므로 이동처리할 수 없다.
9. 이동 방향이 0이 아닐 경우 이동시킬 물고기의 좌표도 변경해 주어야 한다.
10. 만약 물고기의 이동이 성공했다면 break처리를 하여 다음 물고기로 넘어가야 한다.
11. 물고기를 모두 이동시켰다면 그 다음에 상어의 움직임을 시뮬레이션 해주어야 한다.
12. 상어는 한 번에 여러개의 칸을 이동할 수 있기 때문에 idx변수를 통해 관리를 해준다.
13. idx를 전위증가시켜 무한루프를 진행시킨다.
14. 현재 상어의 방향에 따라 방향배열 값을 * idx를 해주면 범위를 벗어나기 전까지의 진행을 탐색할 수 있다.
15. 만약 맵상에서의 0인 상태 즉 물고기가 이미 잡아먹힌 경우에는 continue 처리를 해준다.
16. 조건에 만족하면 현재 맵 정보를 new_map으로 깊은 복사를 해준다.
17. new_map 상 에서 상어가 있던 위치를 0으로, 이동 위치를 17로 설정하여 상어의 움직임을 기록해 준다.
18. 잡아먹힌 물고기를 방문처리 해준 후 새로운 좌표, 잡아먹은 물고기의 방향 정보, 잡아먹은 물고기의 번호를 val에 더해주고, 새로운 맵과 물고기 정보를 매개변수로 전달하여 재귀를 진행해 준다.
19. 무한루프를 돌던 중 상어가 범위를 벗어나면 break처리를 해준다.
20. 현재 val을 max_val과 비교하여 더 큰값으로 변경해 준 뒤 재귀를 마쳐준다.
21. 재귀가 돌아오고 나서는 잡아먹은 물고기 정보를 다시 원상복구 시켜준다.

 

문제풀이

1. input 함수를 통해 입력값을 받아 초기 맵과 물고기 정보를 저장해준다.
2. init 함수를 통해 초기 정보 값을 변경해 준다.
3. bt 함수에 시작 좌표 0, 0과 해당 좌표에 있던 물고기의 방향 정보, 번호, 초기 맵과 물고기 정보를 매개변수로 전달하여 백트래킹을 시작해 준다.
4. max_val에 저장되어 있는 값을 출력해 준다.

 

참고 사항

매 재귀마다 맵과 물고기 정보를 깊은 복사를 한 후에 넘겨주어야 한다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int v[17];
int max_val, sdir;

struct Fish {
	int x, y, dir;
};

vector<Fish> fishes(18);
vector<vector<int>> lst(4, vector<int>(4));

void input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b; cin >> a >> b;
			lst[i][j] = a;
			fishes[a] = { i, j, b - 1 };
		}
	}
}

void init() {
	max_val = lst[0][0];
	sdir = fishes[lst[0][0]].dir;
	v[lst[0][0]] = 1;
	lst[0][0] = 17;
}

void bt(int x, int y, int dir, int val, vector<vector<int>> map, vector<Fish> cur) {
	vector<Fish> temp = cur;
	for (int i = 1; i <= 16; i++) {
		if (v[i]) continue;
		Fish& fish = temp[i];
		int cx = fish.x, cy = fish.y, cd = fish.dir;
		for (int i = 0; i < 8; i++) {
			int nx = cx + dx[(cd + i) % 8], ny = cy + dy[(cd + i) % 8];
			if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && map[nx][ny] != 17) {
				if (map[nx][ny]) {
					Fish& target = temp[map[nx][ny]];
					target.x = cx;
					target.y = cy;
				}
				fish = { nx, ny, (cd + i) % 8 };
				swap(map[cx][cy], map[nx][ny]);
				break;
			}
		}
	}

	int idx = 0;
	while (++idx) {
		int nx = x + dx[dir] * idx, ny = y + dy[dir] * idx;
		if (0 <= nx && nx < 4 && 0 <= ny && ny < 4) {
			if (!map[nx][ny]) continue;
			vector<vector<int>> new_map = map;
			new_map[x][y] = 0;
			new_map[nx][ny] = 17;
			v[map[nx][ny]] = 1;
			bt(nx, ny, temp[map[nx][ny]].dir, val + map[nx][ny], new_map, temp);
			v[map[nx][ny]] = 0;
		}
		else break;
	}
	max_val = max(max_val, val);
	return;
}

int main() {
	input();
	init();
	bt(0, 0, sdir, max_val, lst, fishes);
	cout << max_val;
}