[백준/파이썬] 16236번 아기 상어

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

16236번: 아기 상어

문제 해석

 

9에 위치한 아기 상어가 있다. 아기 상어는 처음 크기가 2 이며, 크기가 자신보다 작은 물고기만 먹을 수 있다. 자신의 크기만큼 물고기를 먹으면 크기가 1 증가한다. 즉 크기가 2 일때 물고기를 두번 먹으면 3으로 커진다.

아기 상어는 자신보다 큰 물고기를 지나갈 수 없으며 자신과 크기가 같은 물고기는 지나갈 수 있다.

가장 가까운 물고기, 가장 위에, 가장 왼쪽에 존재하는 물고기를 먼저 먹는다고 할 때 물고기를 잡아먹을 수 있는 시간을 구하여라.

---

코드

 

from collections import deque
input = __import__('sys').stdin.readline

n = int(input())
arr = []
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]

for i in range(n):
    temp = list(map(int, input().split()))
    arr.append(temp)
    for j in range(n):
        if arr[i][j] == 9: 
            sx, sy = i, j
            arr[i][j] = 0

def bfs(sx, sy):
    visit = [[0] * n for _ in range(n)]
    q = deque()
    level = 2
    exp = 0
    q.append((sx, sy, 0))
    visit[sx][sy] = 1
    ans = 0
    
    while 1:
    # x, y, dist
        canEat = []
        while q:
            i, j, move = q.popleft()
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if not(0 <= x < n and 0 <= y < n): continue
                if visit[x][y]: continue
                if arr[x][y] <= level:
                    # 0 또는 자신과 같은 크기라면 그냥 이동
                    if arr[x][y] == 0 or arr[x][y] == level:
                        visit[x][y] = 1
                        q.append((x, y, move + 1))
                    # 물고기 라면 canEat 배열에 넣고 이동
                    else:
                        canEat.append((x, y, move + 1))
                        visit[x][y] = 1
                        q.append((x, y, move + 1))
        # canEat 에서 먹을 물고기 선택 후 다시 bfs
        # canEat이 비어 있다면 더이상 먹을 고기가 없으므로 return
        if canEat:
            # 거리가 가장 가깝고, 가장 위에, 왼쪽에 존재하는 좌표
            canEat = sorted(canEat, key = lambda x: [x[2], x[0], x[1]])
            x, y, move = canEat[0]
            
            # 다시 BFS 큐 초기화, 경험치 += 1, 먹은 위치 0만들기, visit 배열 초기화, ans 값 갱신
            q = deque()
            exp += 1
            arr[x][y] = 0
            visit = [[0] * n for _ in range(n)]
            visit[x][y] = 1
            q.append((x, y, move))
            ans = move
            # 아기 상어가 자신만큼 먹을 경우 (크기 + 1)
            if exp == level:
                exp = 0
                level += 1
        else: return ans
        
print(bfs(sx, sy))

---

문제 풀이

 

기본 매커니즘은 시작 부분에서 BFS로 탐색하여 먹을 수 있는 물고기의 좌표, 거리(시간)을 canEat 배열에 넣었다.

canEat배열에서 거리, x, y 순으로 내림차순으로 정렬한 뒤 초기값, 상어의 크기, 거리(시간)을 갱신해 주었다.

이를 canEat 배열이 비어있을때 까지 반복하여 답을 구했다.

 

문제에서 주어지는 구현 조건을 놓치지 않고 구현만 한다면 쉽게 풀 수 있다!