<Baekjoon> #19263 DFS, Backtracking 청소년 상어 c++

#19236 청소년 상어
참고1 참고2
삼성 SW 기출 문제를 풀 때 유의할 점은 문제에 나와있는 조건을 하나라도 놓치면 안 된다. 각 조건을 정리해보면

물고기
1. 물고기는 번호와 방향을 가지고있다
2. 번호가 작은 물고기부터 이동을 한다
3. 상어가 있는 칸이나 범위 밖으로는 이동할 수 없다
4. 이동할 수 없을 때는 45도 반시계 방향으로 회전한다
5. 만약 이동할 수 없으면 이동하지 않는다
6. 다른 물고기가 있는 칸으로 이동할 때는 그 칸의 물고기와 위치를 바꾼다

상어
1. 처음 (0,0)에 있는 물고기를 먹고 그 방향을 가진다
2. 한 번의 여러 개의 칸을 이동할 수 있다
3. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다
4. 물고기가 있는 칸으로 이동하면 물고기를 먹고 방향을 가진다
5. 이동할 수 있는 칸이 없으면 집으로 간다
6. 이동한다면 다시 물고기가 이동하고 이 과정이 반복된다

이것을 보면 DFS, Backtracking 으로 문제를 해결해야 함을 알 수 있다

1. Initialize

• 물고기의 번호, 좌표, 방향 그리고 생존 여부(상어에게 먹혔는지)를 표시해야 한다

typedef struct Fish {
	int y, x;
	int dir;
	bool alive;
};
vector<Fish> fish;

fish[1] 부터 fish[16]까지 1번~16번 물고기를 차례대로 넣어준다

• vector map[]에는 해당 위치에 있는 물고기의 번호를 저장하고, 처음에 상어가 (0,0)위치의 물고기를 먹고 시작한다 (상어가 있는 위치는 map에서 -1로 표시한다)

int fNum = map[0][0];
int dir = fish[fNum].dir;
fish[fNum].alive = false;
map[0][0] = -1;
dfs(0, 0, dir, fNum);

2. move Shark (DFS)

• void dfs(int y, int x, int dir, int sum)
(y,x): 현재 상어의 위치, dir: 상어가 가진 방향, sum: 상어가 이때까지 먹은 물고기 번호의 합
• 본래의 map과 fish는 변경되면 안 되기 때문에 copyState()에서 이를 저장해두고 나중에 이동이 끝난 후 다시 본래의 값을 복사해준다
  (더 이상 상어가 움직일 수 없을 때 다시 돌아와서 상어를 다른 위치로 이동해서 재탐색 하기 위해)

vector<vector<int>> cMap(4, vector<int>(4));
vector<Fish> cFish = vector<Fish>(17);
copyState(cMap, map, cFish, fish);

• 물고기가 이동한 후 상어가 이동한다

	//상어는 최대 3번 이동할 수 있다
	for (int i = 1; i <= 3; i++) {
		int ny = y + dy[dir] * i;
		int nx = x + dx[dir] * i;
		
		if (ny >= 0 && nx >= 0 && ny < 4 && nx < 4) {
       		 //이동할 위치가 빈칸이라면 이동하지 못한다
			if (map[ny][nx] == 0) continue;

			//먹는 물고기 번호와 방향을 저장
			int fishNum = map[ny][nx];
			int nDir = fish[fishNum].dir;

			makeState(y, x, ny, nx, fishNum, true);
			dfs(ny, nx, nDir, sum + fishNum);
			makeState(y, x, ny, nx, fishNum, false);
		}
		else break;
	}
	copyState(map, cMap, fish, cFish);
}

상어가 원래 있던 위치 (y,x), 상어가 이동할 위치 (ny,nx), 상어가 이동할 위치에 있는 물고기 번호 (fishNum)을 makeState 함수에 넘기면 이 함수에서는 상어가 이동하고 난 후 변화를 만들어준다.
그리고 상어가 더 이상 움직일 수 없을 때까지 이동이 끝난 후에는 다시 원래 상태로 되돌려준다.

void makeState(int y, int x, int ny, int nx, int fishNum, bool alive) {
	if (alive) {
		map[y][x] = 0;
		map[ny][nx] = -1;
		fish[fishNum].alive = false;
	}
	else {
		map[y][x] = -1;
		map[ny][nx] = fishNum;
		fish[fishNum].alive = true;
	}
}

3. move Fish

• dfs 함수에서 현재 상어의 위치를 가져온다 (shark_y, shark_x)
• 물고기는 1번부터 16번까지 모두 움직인다 (죽은 물고기 제외)
• 물고기가 움직이는 위치를 ny,nx에 저장해주고 이 (ny,nx)가 map의 범위 내에 있고, 움직일 위치에 상어가 없을 때까지 45도 반시계 방향으로 회전해준다

while (ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || 
			(shark_y == ny && shark_x == nx)) {
	dir++;
	if (dir == 9) dir = 1;
	ny = y + dy[dir];
	nx = x + dx[dir];
}

• 이동할 위치가 비어 있는 경우 그냥 이동하고, 물고기가 있는 경우에 두 물고기를 바꾸어준다

//move to empty map
if (map[ny][nx] == 0) {
	fish[i].y = ny;
	fish[i].x = nx;
	fish[i].dir = dir;
	map[ny][nx] = i;
	map[y][x] = 0;
}
//swap fish
else if (map[ny][nx]!=-1) {
	int idx = map[ny][nx];
	fish[idx].y = y;
	fish[idx].x = x;
	fish[i].y = ny;
	fish[i].x = nx;
	fish[i].dir = dir;
	swap(map[y][x], map[ny][nx]);
}

전체코드

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

using namespace std;

const int dy[9] = {0,  -1, -1, 0, +1, +1, +1, 0, -1 };
const int dx[9] = { 0, 0, -1, -1, -1, 0, +1, +1, +1 };

typedef struct Fish {
	int y, x;
	int dir;
	bool alive;
};

int answer;
//map state: -1=shark, 0= empty, else =fish num 
vector<vector<int>> map(4, vector<int>(4));
vector<Fish> fish;

void copyState(vector<vector<int>>&a, vector<vector<int>>&b, vector<Fish> &c, vector<Fish>&d) {
	for (int i= 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			a[i][j] = b[i][j];
	for (int i = 1; i <= 16; i++)
		c[i] = d[i];
}

void moveFish(int shark_y, int shark_x) {
	for (int i = 1; i <= 16; i++) {
		if (fish[i].alive == false) continue;

		int y = fish[i].y;
		int x = fish[i].x;
		int dir = fish[i].dir;

		int ny = y + dy[dir];
		int nx = x + dx[dir];

		//out of range OR there will be a shark 
		while (ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || (shark_y == ny && shark_x == nx)) {
			dir++;
			if (dir == 9) dir = 1;
			ny = y + dy[dir];
			nx = x + dx[dir];
		}
		//move to empty map
		if (map[ny][nx] == 0) {
			fish[i].y = ny;
			fish[i].x = nx;
			fish[i].dir = dir;
			map[ny][nx] = i;
			map[y][x] = 0;
		}
		//swap fish
		else if (map[ny][nx]!=-1) {
			int idx = map[ny][nx];
			fish[idx].y = y;
			fish[idx].x = x;
			fish[i].y = ny;
			fish[i].x = nx;
			fish[i].dir = dir;
			swap(map[y][x], map[ny][nx]);
		}
	}
}

void makeState(int y, int x, int ny, int nx, int fishNum, bool alive) {
	if (alive) {
		map[y][x] = 0;
		map[ny][nx] = -1;
		fish[fishNum].alive = false;
	}
	else {
		map[y][x] = -1;
		map[ny][nx] = fishNum;
		fish[fishNum].alive = true;
	}
}

void dfs(int y, int x, int dir, int sum) {
	answer = max(answer, sum);
	vector<vector<int>> cMap(4, vector<int>(4));
	vector<Fish> cFish = vector<Fish>(17);
	copyState(cMap, map, cFish, fish);

	moveFish(y,x);

	for (int i = 1; i <= 3; i++) {
		int ny = y + dy[dir] * i;
		int nx = x + dx[dir] * i;
		
		if (ny >= 0 && nx >= 0 && ny < 4 && nx < 4) {
			if (map[ny][nx] == 0) continue;

			int fishNum = map[ny][nx];
			int nDir = fish[fishNum].dir;

			makeState(y, x, ny, nx, fishNum, true);
			dfs(ny, nx, nDir, sum + fishNum);
			makeState(y, x, ny, nx, fishNum, false);
		}
		else break;
	}
	copyState(map, cMap, fish, cFish);
}

void init() {
	//fish[1]~fish[16] 
	fish = vector<Fish>(17);
	//input data to map, vector fish
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int num, dir;
			cin >> num >> dir;
			map[i][j] = num;
			fish[num] = { i,j,dir,true };
		}
	}
	//initialize
	int fNum = map[0][0];
	int dir = fish[fNum].dir;
	fish[fNum].alive = false;
	map[0][0] = -1;
	dfs(0, 0, dir, fNum);
}

int main() {
	init();
	cout << answer << endl;
	return 0;
}

이렇게 써놓고 나니까 별 거 아닌 거 같은데 문제 풀고 에러 찾는다고 디버깅 하루종일 찍고.. 거의 이틀 가까이 걸렸다.. 눈물..

1. 문제를 꼼꼼하게 읽지 않아서 조건들을 제대로 이해하지 못한 것
2. vector에서 범위를 넘는 값을 참조해서 계속 런타임 에러가 났던 것
3. 방향을 저장할 때 1부터 값을 넣어서 index가 계속 헷갈렸던 것