본문 바로가기

Programming/BOJ

BOJ 16236 · 아기 상어


알고리즘 분류 : BFS  


아기 상어가 물고기를 먹으면서 움직이는 최단 거리를 구하는 문제다. 여러 가지 조건이 까다로운 문제다. 첫 번째, 아기 상어는 자신보다 크거나 같은 크기의 물고기를 먹을 수 없다. 두 번째, 상어에게 가장 가까운 위치에 있는 물고기를 우선순위로 먹어야 한다. 세 번째, 여러 마리가 가까이에 있다면, 가장 위쪽에 있는 물고기, 그다음 순서로 가장 왼쪽에 있는 물고기를 우선순위로 먹어야 한다. 이 세 가지 조건을 모두 만족하면서 BFS 탐색을 하기 위해서는, 최소 힙(Min Heap)이 구현된 우선순위 큐(Priority Queue)를 사용하면 된다.


  • 상어의 크기(body), 물고기를 먹은 횟수(eat)를 별도로 저장하는 변수를 둔다.
  • BFS에 사용할 큐를 우선순위 큐로 대체한다. C++의 경우 priority_queue가 기본적으로 Max Heap이므로, 연산자 오버로딩을 통해 Min Heap으로 바꿔야 한다. 또는 음수로 처리하면 Min Heap처럼 이용할 수 있다. 파이썬은 Heapq를 사용하면 된다.
  • Min Heap의 우선순위는 이동 거리(d), 행 좌표(x), 열 좌표(y) 순위로 둔다. 문제에 주어진 우선순위가 거리가 가까운 것, 가장 위쪽, 가장 왼쪽 순서이기 때문이다.
  • 물고기의 크기가 상어보다 크거나 같다면, 먹지 못하는 경우이므로 무시하고 지나가면 된다.
  • 상어가 물고기를 먹기 전까지, 움직일 때마다 이동거리를 1씩 증가시킨다.
  • 움직이다가, 상어 크기보다 작은 크기의 물고기를 발견하면 먹는다. 먹은 칸을 0으로 바꾼다. 정답에 현재까지 이동한 거리를 더한다. 먹은 횟수를 1 증가시킨다. 
  • 만약 먹은 횟수가 상어의 크기와 같다면, 상어 크기를 1 증가시키고, 먹은 횟수를 0으로 만든다.
  • 다음 물고기를 먹기 위해 움직일 때, 이미 갔던 곳을 다시 방문할 수도 있다. 따라서 거리와 방문 체크 배열을 모두 초기화한다. 큐에 들어있는 좌표도 비운다.
  • 더 이상 먹을 수 있는 물고기가 없다면 종료한다.


✓ 4번 예제 테스트케이스를 설명하기 위한 그림이다.

✓ 굵은 숫자 : 입력으로 주어진 물고기 크기 / 순서 : 상어가 움직이는 순서 / 거리 : 상어가 이동한 누적 이동거리 / 크기: 현재 상어의 크기




C++ 소스코드


#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct shark {
    int d, x, y;
    // Min Heap (priority : distance > x position > y position)
    bool operator < (const shark &t) const {
        if (d == t.d) {
            if (x == t.x) return y > t.y;
            else return x > t.x;
        } else return d > t.d;
    }
};

int n, body, eat, ans;
int a[20][20];
bool check[20][20];
priority_queue<shark> q;
const int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};

void bfs() {
    while (!q.empty()) {
        int d = q.top().d, x = q.top().x, y = q.top().y;
        q.pop();
        // Shark can eat fish, if fish is smaller than shark.
        if (0 < a[x][y] && a[x][y] < body) {
            // Count eating fish.
            a[x][y] = 0;
            eat++;
            // Body size + 1
            if (eat == body) {
                body++;
                eat = 0;
            }
            ans += d;
            // Initializing distance, visited check, and queue.
            d = 0;
            memset(check, false, sizeof(check));
            while (!q.empty()) q.pop();
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            // Cannot pass if fish is bigger than shark, or already visited.
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (check[nx][ny]) continue;
            if (0 < a[nx][ny] && a[nx][ny] > body) continue;
            // Update next moving.
            q.push({d+1, nx, ny});
            check[nx][ny] = true;
        }
    }
}

void solve() {
    body = 2;
    bfs();
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 9) {
                q.push({0, i, j});
                a[i][j] = 0;
            }
        }
    }
    solve();
    return 0;
}


✓ STL 중 하나인, tuple을 이용하면 더 간결하다. tuple은 여러 개의 변수에 대해 우선순위가 순서대로 구현되어 있다.

✓ 소스코드 보기




Python 3 소스코드


from sys import stdin
from heapq import heappush, heappop
input = stdin.readline

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
q = []

def init():
    for i in range(n):
        for j in range(n):
            if a[i][j] == 9:
                heappush(q, (0, i, j))
                a[i][j] = 0
                return

def bfs():
    body, eat, ans = 2, 0, 0
    check = [[False]*n for _ in range(n)]
    while q:
        d, x, y = heappop(q)
        if 0 < a[x][y] < body:
            eat += 1
            a[x][y] = 0
            if eat == body:
                body += 1
                eat = 0
            ans += d
            d = 0
            while q:
                q.pop()
            check = [[False]*n for _ in range(n)]
        for dx, dy in (-1, 0), (0, -1), (1, 0), (0, 1):
            nd, nx, ny = d+1, x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if 0 < a[nx][ny] > body or check[nx][ny]:
                continue
            check[nx][ny] = True
            heappush(q, (nd, nx, ny))
    print(ans)

init()
bfs()




참고



태그

  • 백준 2019.04.05 18:54 신고 댓글주소 수정/삭제 댓글쓰기

    안녕하세요 혹시 c++코드에서
    처음 상어가 배치된(9번자리) 자리는 왜 check배열을 true로 하지 않는지 여쭤봐도 될까요?

    • 안녕하세요 😄
      제가 빠트린 것 같습니다. 정확하게 하자면 상어의 첫 위치를 true를 해놓는 게 맞습니다.
      다만, 첫 위치로 돌아간 좌표는 이미 사방이 방문 체크로 돼있어서 더 이상 진행하지 못합니다. 알고리즘에 영향을 주는 부분은 아닙니다.

  • 상어 2019.04.13 02:11 신고 댓글주소 수정/삭제 댓글쓰기

    안녕하세요! 올려주신 해설에 많은 도움을 받아 코드를 직접 짜보는중에 궁금한 점이 생겨서 질문드립니다..

    for문에서 상하좌우로 움직인 후에 물고기를 먹을 수있는지 판단하는 로직으로 짜보았는데.. 프로그램이 터지더라구요.. 몇시간째 찾아본 결과 올려주신 코드처럼 먼저 먹을수 있는 물고기인지 판단하는 로직으로 짜니 프로그램이 실행됬습니다..

    혹시 for문에서 상하좌우 이동하기 전에 먼저 물고기를 먹을 수 있는건지 아닌 건지 판단하신 이유좀 여쭤볼 수 있을까요?

  • 안녕하세요 상어님! 😄
    티스토리 오류 때문에 답글의 답글이 안되네요. 우선 제 코드를 다시 설명드리자면, BFS 부분은 다음과 같은 흐름으로 진행됩니다.

    *****

    1. 우선순위 큐에서 하나의 좌표를 pop한다. 이 좌표(x, y)는 문제의 3가지 조건을 만족하는 좌표이다.

    2. 꺼낸 현재 위치(x, y)에서 먹을 수 있는 물고기를 찾아본다.

    3-1. 먹을 수 없다면, 다음 위치(nx, ny)로 이동한다.
    * 현재 이동 거리가 D일 때, D+1로 이동할 수 있는 모든 좌표가 우선순위 큐에 들어있음.

    3-2. 먹을 수 있다면, 먹은 횟수에 따라 물고기 사이즈를 처리하고, 우선순위 큐와 방문 체크 배열을 초기화한다. 먹은 위치의 좌표에서 다음 위치(nx, ny)로 이동한다.
    * 우선순위 큐를 비웠으므로, 다음 위치는 단 하나의 좌표(x, y)에서만 상하좌우를 살펴본다. (즉, 상어 먹은 위치부터 BFS를 새로 시작)

    4. 다음으로 이동할 수 있는 위치를 모두 찾고, 이동 가능한 모든 좌표를 우선순위 큐에 집어넣는다.

    *****

    제 코드 흐름을 요약하자면, "먹을 수 있는 물고기를 모두 찾고 → 그중에 우선순위가 가장 높은 물고기만 먹은 후 → BFS를 새로 시작한다"입니다.
    즉, 상하좌우를 살펴보는 과정에서는 이동 가능한 모든 좌표를 우선순위 큐에 넣어야 합니다.
    만약 상하좌우를 살펴보는 과정에서 물고기 먹는 것을 처리하면, 문제의 3가지 조건에 부합하지 않는 물고기를 먹는 경우가 생길 수밖에 없습니다.