[알고리즘] 백준 16236번: 아기 상어 (C++), 빡구현! 그리고, DFS, BFS에 관한 이야기 (개인적으로 꼭 명심)

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

16236번: 아기 상어

---

문제에 들어가기 앞서 (1)

이번 문제는 이때까지 겪어온 '빡구현' 문제들을 애기로 만들어버리는 수준이다.

걸어야 할 조건들이 엄청 많다.

 

1) 처음엔 DFS로 했을 때, DFS로는 안 되겠다. BFS로 해야지. (종료 조건이 없었음)

2) BFS로 했을 때, 이 무한 루프 어떻게 처리하지?

3) 방문 체크를 해야겠구나? 그러면.. 따질 게 많은데 싹 갈아엎어야 하나?

 

2번을 갈아엎었다. 조건들이 엄청 많았기에 설명이 잘 되어있는 블로그를 찾았다.

(+참고 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4)

>> 설명을 엄청 잘해주셨다. 나도 나름대로 주석을 잘 활용하고 있다고 생각했는데 이 분 코드 주석을 읽으면 부족했다는 것을 알게 된다.

---

문제에 들어가기 앞서 (2)

10월 회고록에서 DFS와 BFS의 차이를 정리해두어야겠다는 말을 했었다.

그것보다 더 크게 아차 싶었던 건 다른 알고리즘과 달리 DFS와 BFS에 대한 생각이었다.

DFS와 BFS는 코드가 길다 보니 평소에 가지고 있던 가치관(?) '알고리즘은 기법이다.'와 벗어났다.

BFS라는 키워드가 떠올랐다고 해서 문제가 풀리는 것은 아니다.

DFS와 BFS 또한 기법이라는 생각을 가지고 있어야 한다.

문제가 있으면 이 기법을 문제를 해결하는 데에 있어서 한 요소라고 생각해야 한다.

다른 알고리즘들도 항상 마찬가지!

 

>> 빨리 DFS, BFS 응용 차이도 포스팅하기!

---

1) 처음엔 DFS로 했을 때, DFS로는 안 되겠다. BFS로 해야지. (종료 조건이 없었음)

이 문제는 DFS로 풀려고 구현을 했었다. BFS로는 방법이 떠오르지 않았기 때문이다. DFS로 구현을 다 하고 나서야 DFS의 답을 구하는 경로를 제외한 경로들은 DFS를 종료시킬 수 없는 조건이 없어서 무한 루프를 발생시키는 것을 알게 되었다.

// 상어 초기 크기 2
// 상하좌우 이동 가능
// 상어의 크기보다 큰 칸은 못 지나감, == 자기랑 크기가 같은 건 갈 수 있음
// 상어 크기보다 작은 칸만 먹을 수 있음
// 상 1, 좌 2 우선
// 
#include <iostream>
using namespace std;

int n;
int map[21][21];
int food = 0;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

void dfs(int row, int col, int cnt, int time, int shark, int sharkCnt) {
	if (cnt == food) {
		cout << time;
		return;
	}

	for (int i = 0; i < 4; i++) {
		int dy = row + dir[i].y;
		int dx = col + dir[i].x;
		if (dy >= 1 && dy <= n && dx >= 1 && dx <= n) {
			if (map[dy][dx] <= shark) {
				// 지나갈 수 있는 길
				if (map[dy][dx] == 0 || map[dy][dx] == shark) {
					// 그냥 지나가는 길
					dfs(dy, dx, cnt, time + 1, shark, sharkCnt);
				}
				else if (map[dy][dx] < shark) {
					if (shark == sharkCnt) {
						dfs(dy, dx, cnt + 1, time + 1, shark + 1, 0);
					}
					else {
						dfs(dy, dx, cnt + 1, time + 1, shark, sharkCnt + 1);
					}
				}
			}
			else {
				// 못 가는 길
				continue;
			}
		}
	}
}

int main() {
	cin >> n;
	int idx;
	int row = 0, col = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> idx;
			map[i][j] = idx;
			if (idx == 9) {
				row = i;
				col = j;
			}
			else if (idx >= 1 && idx <= 6) {
				food++;
			}
		}
	}

	if (row == 0 && col == 0) {
		return 0;
	}
	else {
		dfs(row, col, 0, 0, 2, 0);
	}
}

---

2) BFS로 했을 때, 이 무한 루프 어떻게 처리하지?

Shark 자체를 구조체로 선언하여 BFS로 처리하려 했다.

방문 체크를 안 한 이유는 다시 갔던 길을 돌아가는 경우가 있어서 따로 방문 체크 처리를 하지 않았었다.

 

반례가 있었다.

3
9 0 0
4 4 4
1 1 1

이 케이스는 방문을 체크하지 않다 보니 1행에서 좌우로 왔다 갔다 거리기만 한다.

또한, 무슨 이유에서인지 밝혀내지는 못 했으나 주어진 TC도 무한 루프를 발생시킨다.

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

// 현재 문제: BFS에 visited가 없으니 무한 루프가 발생함
// 떠오르는 아이디어: visited를 사용하고 한 번 BFS가 끝나고 다음 BFS를 돌리면 되지 않을까

int n;
int map[21][21];
int food = 0;
int foodCntMax = 0;

typedef struct {
	int y;
	int x;
	int body; // 현재 몸 크기
	int foodCnt; // 현재 먹은 먹이
	int time; // 현재 어느 정도 시간을 썼는가
} Shark;

typedef struct {
	int y;
	int x;
} Direction;

Direction dir[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

void bfs(int row, int col) {
	queue<Shark> shark;
	shark.push({ row, col, 2, 0, 0 });
	while (!shark.empty()) {
		int y = shark.front().y;
		int x = shark.front().x;
		int body = shark.front().body;
		int foodCnt = shark.front().foodCnt;
		int time = shark.front().time;

		if (foodCnt == food) {
			cout << time;
			return;
		}

		shark.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= n) {
				if (map[dy][dx] == 0 || map[dy][dx] == body) {
					shark.push({ dy, dx, body, foodCnt, time + 1 });
				}
				else if (map[dy][dx] < body) {
					if (foodCnt == body) {
						shark.push({ dy, dx, body + 1, 0, time + 1 });
						map[dy][dx] = 0; // 먹이를 먹었으니 없애야 함
					}
					else {
						shark.push({ dy, dx, body, foodCnt + 1, time + 1 });
						map[dy][dx] = 0;
					}
				}
			}
		}
	}
}

int main() {
	cin >> n;
	int idx;
	int row = 0, col = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> idx;
			map[i][j] = idx;
			if (idx == 9) {
				row = i;
				col = j;
			}
			else if (idx >= 1 && idx <= 6) {
				food++;
			}
		}
	}

	bfs(row, col);
}

 

---

3) 방문 체크를 해야겠구나? 그러면.. 따질 게 많은데 싹 갈아엎어야 하나?

이쯤에서 링크를 걸었던 블로그를 참고했다. (https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4)

난 조금 더 현실감(?)을 주기 위해 shark의 구조체 선언에 size와 foodCnt까지 넣어주고, shark를 전역 변수로 선언했다.

[포인트]

문제에 들어가기 앞서(2)에서 말한 대로 '모든 알고리즘은 기법이다'가 조금조금 적용되던 DFS, BFS를 확실히 적용시키는 계기가 되었다. BFS를 한 번 돌리고, 사이즈가 커질 정도로 먹었는지, 먹은 자리 초기화, 시간을 더해주는 게 확실히 DFS와 BFS를 기법 취급해주는 느낌이 들었다.

 

생각에 대한 포인트와 별개로 정말 포인트라고 느꼈던 건 최단 경로가 바뀌는 것을 먹이를 먹은 걸로 취급한다는 게 핵심이었던 거 같다.

 

그리고, 위가 우선이고, 왼쪽이 다음 우선이 되는 것을 표현하는 것도 신기했다. 난 당연히 for를 4가지 방향 돌릴 때, 위를 우선시하게끔 Direcion 4가지 방향 배열을 선언할 때, 우선적인 순서로 작성했기에 저런 방법이 있을 거라고는 생각 못했다. Direction 방향을 그렇게 선언한 것 또한 위를 우선적으로 탐색할 거라는 확신이 들지 않았었기에 저런 방법이 있다는 것에 생각을 하게 했다.

 

정리하자면

1) BFS를 하나의 기법으로 사용했던 포인트 >> 더 논리적인 코드가 도출되는 점

2) BFS를 하나의 방법 그 자체로 보다 보니 BFS에서 한 번에 해결하려 했다는 점

3) 위와 왼쪽 방향을 우선적으로 찾는 것

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
#define intMAX 21
#define valMAX 401

int n;
int map[21][21] = { 0, };
int check[21][21] = { 0, }; // 이동거리 저장
int minDist, minX, minY;
int result = 0;

typedef struct {
	int y, x;
	int size;
	int foodCnt;
} Shark;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
Shark shark;

void init_check() {
	minDist = valMAX;
	minX = intMAX;
	minY = intMAX;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			check[i][j] = -1;
		}
	}
}

void bfs(int row, int col) {
	queue<pair<int, int>> q;
	check[row][col] = 0;
	q.push(make_pair(row, col));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;

			// 벗어나면 건너뜀
			if (dy < 1 || dy > n || dx < 1 || dx > n) {
				continue;
			}
			// 이미 방문했거나 현재 상어의 사이즈보다 크면 건너뜀
			if (check[dy][dx] != -1 || map[dy][dx] > shark.size) {
				continue;
			}
			// 이동거리 계산
			check[dy][dx] = check[y][x] + 1;

			// 먹을 수 있는 물고기의 경우
			if (map[dy][dx] != 0 && map[dy][dx] < shark.size) {
				// 최단 경로가 나올 경우
				if (check[dy][dx] < minDist) {
					minY = dy;
					minX = dx;
					minDist = check[dy][dx];
				} // 최단 경로 거리가 같을 경우
				else if (minDist == check[dy][dx]) {
					if (minY == dy) { // 행 >> 즉 위아래 높이가 같다면 좌우 비교
						if (minX > dx) {
							// minX가 더 오른쪽에 있다면 최단 경로 바꾸기
							minY = dy;
							minX = dx;
						}
					}
					else if (minY > dy) {
						// 최단 경로가 같을 때이기 때문에 위아래로 짧은 거 선택
						minY = dy;
						minX = dx;
					}
				}
			}

			// 다음 이동을 위한 큐 삽입
			q.push(make_pair(dy, dx));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	shark.size = 2;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];

			if (map[i][j] == 9) {
				shark.y = i;
				shark.x = j;
				// 지도상에서 0으로 바꾸어준다.
				map[i][j] = 0; // 굳이 바꿔주는 이유가 있을까?
			}
		}
	}

	while (1) {
		init_check();

		// 먹이를 하나 먹을 때마다 갱신을 해준다.
		// BFS는 일종의 도구로 쓰였다.
		// 먹이를 먹는 과정에 신경쓰지 않았다.
		bfs(shark.y, shark.x);

		if (minY != intMAX && minX != intMAX) {
			//다르다는 조건이 성립하는 것은 먹을 수 있는 물고기를 찾았다는 말이다.

			//먹이를 먹기까지 걸린시간을 더해준다.
			result += check[minY][minX];

			// 먹이를 먹었으니 foodCnt++
			shark.foodCnt++;

			// 자신의 사이즈만큼 먹었으면 커지기 때문에
			// 푸드 카운트를 0으로 두고, 사이즈를 키운다.
			if (shark.foodCnt == shark.size) {
				shark.size++;
				shark.foodCnt = 0;
			}

			// 먹이를 먹은 자리에는 먹이가 없다.
			// 초기화 필수!
			map[minY][minX] = 0;

			// 상어의 현재 위치를 업데이트 해준다.
			shark.y = minY;
			shark.x = minX;
		}
		else {
			// 먹은 게 없으면 minY와 minX값이 같다.
			break;
		}
	}

	cout << result;
	return 0;
}

---

느낀 점

글을 잘 못 쓰다 보니 글로써 느낀 것들이 잘 정리되지는 않은 느낌이지만 최대한 잘 써보려 했다. 여러모로 꼭 무조건 업 솔빙 해야 한다!