[BFS]BOJ 16236_아기 상어

문제 링크 : www.acmicpc.net/problem/16236

16236번: 아기 상어

 

삼성 SW 역량 테스트 기출문제이다.

이 문제도 전형적인 2차원 배열에서의 BFS 문제이지만, 단순 BFS로는 해결되지 않는 부분이 있다.

 

문제의 조건에서,

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

라고 제시되었기 때문에

BFS를 실행할 때 큐에 삽입되는 물고기들의 좌표들의 조정이 필요하다.

 

가령, 이 경우를 보자.

각 칸에 적힌 숫자는 북-동-남-서 순서로 탐색할 때 각 칸이 탐색되는 순서이다.

이 경우에서 11번 칸의 물고기가 13번 칸의 물고기보다 먼저 탐색되는데,

문제의 조건에서 13번에 있는 물고기가 먼저 먹혀야 한다.

따라서, 물고기들을 큐에 넣을 때 row, col 이 작은 순으로 정렬해서 넣어야 한다.

이 과정에서, 우선순위 큐(Priority Queue)가 사용된다.

 

물고기들을 좌표를 기준으로 정렬해서 큐에 넣었을 때, 이런 경우도 보자.

이 경우 (1, 1)의 물고기가 (1, 3)에 있는 물고기보다 거리가 더 멀지만,

좌표 정렬에 의해 (1, 1)의 물고기에게 먼저 먹히게 된다.

따라서, 우선순위 큐의 정렬 기준에 물고기의 거리도 포함시켜야 한다.

즉, 거리 - 행 - 열 순으로 정렬되도록 우선순위 큐를 사용해야 한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
 
int n, range_r, range_c;
int board[21][21], visit[21][21], fishes[9];
int live_time, eat_cnt, level = 2;
p dir[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; //0123-NWSE
priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> que;
pair<int, int> cur_pos;
 
pair<int, int> bfs() {
    que.push({ 0, cur_pos });
 
    while (!que.empty()) {
        pair<int, int> cur = que.top().second;
        que.pop();
 
        //현재 먹을 수 있는 물고기라면 함수 종료
        int v = board[cur.first][cur.second];
        if (v > 0 && v < level) {
            eat_cnt++;
            board[cur.first][cur.second] = 0;
            live_time += visit[cur.first][cur.second];
            return cur;
        }
 
        for (int i = 0; i < 4; i++) {
            int newR = cur.first + dir[i].first;
            int newC = cur.second + dir[i].second;
            if (newR < 1 || newR > n || newC < 1 || newC > n) continue;
            if (visit[newR][newC] > 0 || board[newR][newC] > level) continue;
 
            visit[newR][newC] = visit[cur.first][cur.second] + 1;
            que.push({ visit[newR][newC], { newR, newC } });
        }
    }
    return { -1, -1 };
}
 
void init() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int val;
            cin >> val;
            if (val == 9) cur_pos = { i, j };
            else {
                board[i][j] = val;
                fishes[val]++;
            }
        }
}
 
int main() {
    init();
 
    while (1) {
        memset(visit, 0, sizeof(visit));
        pair<int, int> result = bfs();
        if (result.first == -1) break;
        if (eat_cnt == level) { level++; eat_cnt = 0; }
        cur_pos = result;
        while (!que.empty()) que.pop();
    }
    printf("%d\n", live_time);
    return 0;
}