프로그래밍/알고리즘

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()



참고



반응형
저작자표시 비영리 변경금지