[BOJ] 16236. 아기 상어

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

16236번: 아기 상어

 

 

1. 해결방법

일단 로직 생각하는데 오래 걸렸고, 생각을 코드로 옮기는데에도 중간중간 디버깅을 많이 해서 골드 4, 5문제보다 두배정도 걸렸다.
5~6시간 정도;;

코드로 옮기려는데 생각보다 조건이 까다로웠다.

작은 물고기만 먹을 수 있음
같은 사이즈의 물고기는 지나갈 수만 있음
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다
상어크기가 2면 2마리 먹어야함

위의 과정을 생각하면서 코드로 옮기면 된다. 그게 어렵다;;

먼저 BFS라는 것을 알아야 한다. 본인은 꽤 걸림,,
먹을 수 있는 먹이를 최단 경로로 찾아야 하기 때문이다.

아기 상어가 있는 자리에서 시작해서 BFS를 돈다.

상하좌우로 돌면서, chk 방문 2차원 배열을 새로 갱신하고 이동할 때마다 방문 리스트에 +1씩 한다.

먹이가 있고 상어 크기보다 작을 때, 즉, 빈 공간이 아닌 먹이가 있는 공간인데 그 먹이가 상어가 먹을 수 있을 때!
상어가 먹었다는 의미로 dist 리스트에 append한다.

만약 상어 크기와 같거나 빈 공간일 때는 아기 상어가 지나갈 수 있어야 하므로, 큐에 append해서 BFS 함수 내에서 반복한다.

여기서 많이 헷갈렸는데, 다른 분들의 코드의 도움으로 해결한 부분이 있다.
바로 BFS 함수의 return 부분인데, 먹이의 우선순위에 대한 정렬을 했다. (코드 보면 이해됨)
같은 거리의 먹이면 오른쪽, 왼쪽 순서로 우선순위가 정해진다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline
from collections import deque

# input
N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]


# bfs
def bfs(y, x):
    chk = [[False] * N for _ in range(N)]
    q = deque()
    q.append((y, x))
    maps[y][x] = 0
    chk[y][x] = True
    dist = []

    while q:
        ey, ex = q.popleft()

        for k in range(4):
            ny, nx = ey + dy[k], ex + dx[k]
            if 0 <= ny < N and 0 <= nx < N:
                if chk[ny][nx] == False:
                    # 먹이가 상어 크기보다 작을 때,
                    if maps[ny][nx] < shark_size and maps[ny][nx] != 0:
                        chk[ny][nx] = chk[ey][ex] + 1
                        dist.append((chk[ny][nx] - 1, ny, nx))
                    # 상어 크기보다 먹이가 작을 때, 또는 빈 공간일 때,
                    elif shark_size == maps[ny][nx] or maps[ny][nx] == 0:
                        chk[ny][nx] = chk[ey][ex] + 1
                        q.append((ny, nx))

    # 이동 거리가 작은 값부터 우선으로 정렬해야함, -> 거리가 같을 땐, 위 그리고 왼쪽에 있는 먹이한테 우선순위가 있으므로 람다를 사용하여 행, 열
    return sorted(dist, key=lambda x : (x[0], x[1], x[2]))


# main
dy, dx = (0, 1, 0, -1), (1, 0, -1, 0)
shark_size = 2

# 아기 상어 위치와 생선 리스트 생성
for i in range(N):
    for j in range(N):
        if maps[i][j] == 9:
            shark_y, shark_x = i, j
            break

answer = 0
count = 0
while True:
    dist_q = deque(bfs(shark_y, shark_x))

    if not dist_q:
        break

    step, y, x = dist_q.popleft()
    answer += step
    count += 1

    # 상어 크기 증가 로직
    if shark_size == count:
        shark_size += 1
        count = 0

    # 반복하기 위한 값 갱신
    shark_y, shark_x = y, x

print(answer)