[BOJ] 16236: 아기 상어 (C++)

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

16236번: 아기 상어

걸린 시간 : 1시간 40분

---

구조체를 사용해 공부해가며 문제를 풀어서 오랜 시간이 걸렸다. 구조체를 이용한 operator의 재정의를 처음 했고, 처음 하다보니 여러 오류가 많아 오래 걸렸다.

 

문제의 흐름은 다음과 같다.

1. 상어가 이동하지 못할 때까지 이동한다. 하나의 이동은 while문 몸체의 한 번의 실행이다.
2. 한 번의 이동에서는 상어가 있는 지점에서부터 다른 이동할 수 있는 모든 지점까지의 거리를 구한다. 여기서 정렬의 기준이 되는 거리, i 좌표, j 좌표를 모두 사용해야 하기 때문에 이를 담은 구조체를 사용한다.
3. priority queue의 top을 꺼내어 상어가 그곳으로 이동한다. 동시에 board, si, sj, sharksize, sizestack 는 모두 현재 상황을 나타내기 때문에 최신화 해야한다. 만약 priority queue가 비어있다면 그 즉시 실행을 끝낸다.

priority queue에 넣을 때 정렬이 되는 기준이 구조체의 < 연산자인데, 이 방법 말고도 cmp를 이용할 수도 있다. 다만, 개인적으로 priority queue에서 정렬이 직관과는 반대된다고 생각해서 어려웠다. 그래서 이렇게 생각하기로 했다. "파라미터로 들어온 것이 top이 된다." 

예를 들어, 문제는 오름차순 상황, 즉 shark의 dist가 작은 것이 top이 되어야 하는 상황이었다.따라서 파라미터로 들어온 s의 값이 더 작아야 하는 것이다. 따라서 return this->dist > s.dist; 와 같이 작성할 수 있는 것이다.

 

또한, BFS는 셀 수 없을 정도로 많이 나온다. pseudo code 형식으로 처리해야 하는 순서와 목록들을 통째로 암기할 정도가 되면 편할 것이다.

board, dist, queue 선언 및 입력;
int di[], dj[] 선언;
dist배열을 모두 -1로 fill;
// 1. 시작점 처리
queue에 시작노드 삽입;
시작노드 dist를 0으로;
 
while (!q.empty()) {
	// 2. 현재 노드 처리
    int ci, cj = q.top();
    q.pop();
    for (int k = 0; k < 방향 가짓수; k++) {
            // 3. 다음 노드 처리
            int ni, nj = ci + di[k], cj + dj[k];
            // 4. 방문할 것인지
            if (ni와 nj가 범위안에 없다 || 갈 수 없는 곳(벽)이다 || 방문했다) continue; //여기서 방문했는지를 dist[ni][nj]가 -1인지로 체크
            // 5. 방문 처리
            큐에 nx, ny 삽입;
            dist[nx][ny] 최신화;
    }
}

• 1번 시작점 처리와 5번 방문 처리는 같은 맥락이다.
• 2번에서 pop()을 하지 않아서 무한루프가 나오는 경우가 많았다. 조심!
• 4번에서 체크해야 하는 것이 대부분 저렇게 3경우라는 것을 꼭 기억해두자.

 

#include <bits/stdc++.h>
using namespace std;
 
int N, ans;
int board[21][21];
int dist[21][21];
int si, sj, sharksize = 2, sizestack;
int di[4] = {1, 0, 0, -1};
int dj[4] = {0, 1, -1, 0};
 
struct shark {
	int dist;
	int j;
	int i;
	
	bool operator < (shark s) const {
		if (this->dist != s.dist) return this->dist > s.dist;
		else if (this->i != s.i) return this->i > s.i;
		else return this->j > s.j;
	}
};
 
void input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 9) {
				si = i;
				sj = j;
				board[i][j] = 0;
			}
		}
}
 
int bfs (int i, int j) {
	queue<pair<int, int> > q;
	for (int k = 0; k < N; k++)
		fill(dist[k], dist[k] + N, -1);
	q.push({si, sj});
	dist[si][sj] = 0;
	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int ni = ci + di[k];
			int nj = cj + dj[k];
			if (ni < 0 || ni >= N || nj < 0 || nj >= N || dist[ni][nj] != -1 || board[ni][nj] > sharksize)
				continue;
			q.push({ni, nj});
			dist[ni][nj] = dist[ci][cj] + 1;
			if (ni == i && nj == j) break;
		}
	}
	return dist[i][j];
}
 
void solution() {
	while (1) {
		priority_queue<shark> pq;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0 && board[i][j] < sharksize) {
					int dist = bfs(i, j);
					if (dist == -1) continue;
					pq.push(shark{dist, j, i});
				}
			}
		}
		if (pq.empty()) break;
		shark s = pq.top();
		si = s.i;
		sj = s.j;
		board[si][sj] = 0;
		ans += s.dist;
		sizestack++;
		if (sizestack == sharksize) {
			sharksize++;
			sizestack = 0;
		}
	}
}
 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	solution();
	cout << ans;
	return 0;
}