[백준 16236] 아기 상어

🥕 [ 백준 16236 ] 아기 상어

문제 링크

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

 

🍒 문제 분석

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 
그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

아기 상어의 크기는 2로 시작하고, 본인 사이즈만큼 물고기를 먹으면 크기가 1 커진다.

아기 상어와 같은 크기의 물고기는 지나가기만 하고 먹지 못한다.

아기 상어보다 작은 물고기는 먹을 수 있다.

아기 상어보다 큰 물고기는 지나갈 수 없다.

 

더 이상 먹을 물고기가 없을 때 까지 걸리는 시간은?

 

🍓 내 해결 과정

먹이를 먹기 까지의 과정을 bfs 로 처리하였다.

시간 기록 겸, 방문 격자를 기록하기 위해 visited를 초기화하였다.

 

물고기를 먹는 우선순위는, 일단 먹을 수 있는 물고기 좌표에 대해 리스트에 저장한 뒤,

이를 문제의 조건에 따라 정렬하여, 어떤 물고기를 먹는지 정하였고

이에 따라 아기 상어 위치를 정의 및 격자 내 물고기를 지웠다.

 

물고기를 먹는 수를 재서 몸집의 크기를 키우는 코드를 작성하였고,

먹이가 없을 때까지 bfs를 반복하여 실행하였다.

 

🥑 코드

# https://www.acmicpc.net/problem/16236
import sys
from collections import deque

input = sys.stdin.readline


def is_outside(coordi):
    if coordi[0] < 0 or coordi[0] >= n or coordi[1] < 0 or coordi[1] >= n:
        return True
    return False


def bfs(size, start):
    """
    아기 상어는 크기 2부터 시작
    """
    visited = [[0] * n for _ in range(n)]
    que = deque()
    que.append(start)
    res_time = 1e9
    res_coordis = []
    # visited에다가 time 기록 ( 1부터 넣어야 안되돌아감 )
    visited[start[0]][start[1]] = 1
    while que:
        x, y = que.popleft()

        # 더 먼 거리의 물고기면 통과
        if visited[x][y] - 1 > res_time:
            continue

        # 물고기를 먹으면 좌표 기록
        if graph[x][y] and graph[x][y] < size:
            # 물고기와의 최단 거리 업데이트
            res_time = visited[x][y] - 1
            res_coordis.append((x, y))

        for d in direct:
            nx, ny = x + d[0], y + d[1]
            # boder 체크
            if is_outside((nx, ny)):
                continue
            # visited 체크
            if visited[nx][ny]:
                continue
            # 문제 조건 (상어 보다 큰 물고기면 못지나감)
            if graph[nx][ny] > size:
                continue
            visited[nx][ny] = visited[x][y] + 1
            que.append((nx, ny))
    # 다 돌았는데, 물고기가 없다면 time 0 기록
    if not res_coordis:
        return 0, (x, y)
    else:
        # 가장 위, 그리고 그 중에서도 왼쪽에 있는 물고기
        res_coordis.sort()
        graph[res_coordis[0][0]][res_coordis[0][1]] = 0
        return res_time, res_coordis[0]


n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
start = False
# find starting point
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            start = (i, j)
            graph[i][j] = 0
            break
    if start:
        break

# 방향
direct = [(-1, 0), (0, -1), (0, 1), (1, 0)]

ans = 0
size = 2
cnt = 0
t = -1
while t:
    t, coordi = bfs(size, start)
    cnt += 1
    ans += t
    start = coordi
    # 먹을 때마다 cnt 세서 물고기 몸집만큼 먹으면 사이즈 업
    if cnt == size:
        size += 1
        cnt = 0

if t == -1:
    print(0)
else:
    print(ans)


"""
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 
그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
"""

 

 

🍉 깨달은 점 및 정리

1. visited로 시간을 같이 기록할 때 주의할 점은, 값을 1부터 넣어야한다는 것이다.
만약 0으로 시작하게 되면, 방문 안한 노드라 생각되어 되돌아간다.

따라서 1로 시작하고, 답안에서 1을 빼주면 된다.

 

2. 먹이를 먹는 우선순위에 대해 처음에는 단순히 direction의 순서를 통해 조정하려 하였다. (위, 왼쪽을 먼저 가겠끔 해서)

그러나 예외 케이스가 발생하였고, 이렇게 처리하면 안된다는 것을 알았다.

결국 행과 열에 대해 정렬하여 첫번째 값을 찾는다는 식으로 코드를 다시 재구현하였다.

 

3. 갈 수 있는 곳 체크

- border, visited, 문제 조건(상어 크기)