아기 상어
백준 16236
GOLD III
문제 내용
문제 링크
해결 방안
문제가 상당히 길어, 문제 내용 중 필요한 부분만 간추리도록 한다.
- 크기가 N×N인 배열이 주어지고, 해당 배열에 빈칸(0)과 물고기의 크기(1~6), 아기 상어(9)가 숫자로 주어진다.
- 아기 상어는 한 번에 상하좌우로 한 칸씩 움직일 수 있다.
- 각 물고기 크기에 따라 다음과 같은 작업을 수행할 수 있다.
- 자신보다 큰 물고기가 있는 칸: 물고기를 먹거나 지나갈 수 없다.
- 자신과 크기가 같은 물고기가 있는 칸: 물고기를 먹을 수 없으나 지나갈 수는 있다.
- 자신보다 작은 물고기가 있는 칸: 물고기를 먹거나 지나갈 수 있다.
- 빈칸은 항상 지나갈 수 있고, 물고기를 먹은 뒤에는 해당 위치는 빈칸이 된다.
- 먹을 수 있는 물고기가 있다면, 해당 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 여러 마리라면, 이동 가능한 거리 중 가장 가까운 물고기를 먹는다.
- 이동 가능한 거리 내에서 거리가 동일한 물고기에 대해서는 가장 위에 있는 물고기를, 위에 있는 위치가 동일하면 그 중에서도 가장 왼쪽에 있는 물고기를 먹는다.
- 처음 크기는 2로 시작하고, 각각의 크기일 때 크기만큼 물고기를 먹으면 크기가 1 증가한다.
- 먹을 수 있는 물고기가 없을 때까지 반복한다.
즉, 아기 상어의 각 위치를 기준으로 우선순위가 가장 높은 물고기를 선택하여 그 위치로 이동하고, 먹은 물고기에 따라 크기를 조정하며 먹을 수 없는 물고기가 생길 때까지 반복하면 된다. 아기 상어의 위치에서 가장 가까운 물고기를 찾는 방법은 우선순위 큐를 사용하여, 각 위치에 대해 상하 위치를 비교하고 동일한 경우에는 좌우 위치를 비교하며 저장한다. 우선순위 큐에서 위치를 하나씩 꺼내며, 그 위치에서 지나갈 수 있으면서 방문하지 않은 한 칸 앞의 위치를 또 다른 우선순위 큐에 저장한다. 꺼낸 위치에 먹을 수 있는 물고기가 있는 경우에는 그 물고기의 위치로 이동한다. 하나의 우선순위 큐 내에서 먹을 수 없는 물고기가 없다면, 또 다른 우선순위 큐의 모든 위치를 가져오고 위치를 가지고 있던 우선순위 큐를 비운다. 먹을 수 있는 물고기가 나올 때까지 반복하고, 두 큐에 저장된 위치가 없다면 먹을 수 있는 물고기가 없는 것으로 간주한다.
이해를 위해, 이 사이트에 나오는 그림으로 설명된 예제들을 참고하기 바란다.
풀이 코드
#include <iostream>
#include <queue>
using namespace std;
using rc = pair<int, int>;
// 큐에 있는 모든 원소를 비움
void clear(priority_queue<rc ,vector<rc>, greater<rc>> &q) {
while(!q.empty()) q.pop();
}
int main() {
// N×N의 크기 입력
int n;
cin >> n;
// 아기 상어의 현재 위치
rc top;
// N×N의 좌표 내 물고기와 아기 상어 위치 입력
vector<vector<int>> map(n, vector<int>(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> map[i][j];
// 현재 위치가 아기 상어면, 위치만 저장
if(map[i][j] == 9) {
top = {i, j};
map[i][j] = 0;
}
}
}
// 현재 아기 상어의 크기
int size = 2;
// 먹은 물고기의 수
int bite = 0;
// 총 이동 거리(1초당 1칸이므로, 칸 수로 대체 가능)
int cost = 0;
// 현재 탐색 중인 이동 거리(이동할 때의 이동 거리로 계산)
int depth = 0;
// 중복 탐색을 막기 위해 기록
vector<vector<bool>> found(n, vector<bool>(n, false));
// 현재 위치와 다음에 갈 위치 저장
// 행이 더 작은 위치가 앞으로 가고, 동일 행에서는 열이 더 작은 위치가 우선
priority_queue<rc, vector<rc>, greater<rc>> curr;
priority_queue<rc, vector<rc>, greater<rc>> next;
// 우선순위 큐에서 꺼내진 위치 저장
int row, col;
// 현재 아기 상어의 위치부터 시작
curr.push(top);
// 현재 위치 방문 취급
found[top.first][top.second] = true;
// 모든 지역 탐색이 끝날 때까지 실행(다음 depth가 존재하지 않을 때까지)
while(!curr.empty()) {
// 현재 위치부터 탐색
top = curr.top();
curr.pop();
row = top.first, col = top.second;
// 빈칸이 아니면서 자신보다 작은 값이면 먹을 수 있는 물고기로 판단
if(map[row][col] != 0 && map[row][col] < size) {
// 해당 위치를 빈칸으로 하고, 먹은 횟수 추가
map[row][col] = 0;
bite++;
// 만약 먹은 횟수가 크기와 같다면, 크기 1 증가 및 먹은 횟수 초기화
if(bite == size) {
size++;
bite = 0;
}
// 총 이동 거리에 현재 이동 거리 추가
cost += depth;
// 모든 변수 초기화
found = vector<vector<bool>>(n, vector<bool>(n, false));
clear(curr);
clear(next);
depth = 0;
// 현재 위치부터 다시 시작
curr.push(top);
found[top.first][top.second] = true;
}
// 한 번도 방문하지 않은 위치를 탐색하고, 탐색한 위치는 방문한 것으로 간주
// 자신보다 큰 물고기는 지나갈 수 없으므로, 다음 위치에 포함하지 않음
if(row > 0 && !found[row - 1][col] && map[row - 1][col] <= size) {
next.push({row - 1, col});
found[row - 1][col] = true;
}
if(col > 0 && !found[row][col - 1] && map[row][col - 1] <= size) {
next.push({row, col - 1});
found[row][col - 1] = true;
}
if(col < n - 1 && !found[row][col + 1] && map[row][col + 1] <= size) {
next.push({row, col + 1});
found[row][col + 1] = true;
}
if(row < n - 1 && !found[row + 1][col] && map[row + 1][col] <= size) {
next.push({row + 1, col});
found[row + 1][col] = true;
}
// 현재 depth에서 탐색이 종료되면, 다음 depth에서 탐색 진행
if(curr.empty()) {
curr = next;
clear(next);
depth++;
}
}
// 이동 가능한 위치가 없다면, 총 이동 거리 출력
cout << cost << endl;
return 0;
}