[백준] 16236 - 아기 상어(파이썬, Python)

출처: https://www.acmicpc.net

www.acmicpc.net/problem/16236

16236번: 아기 상어

해당 문제 '엄마 상어의 도움이 없이 먹이(물고기)를 먹을 수 있는 시간'을 계산하는 문제입니다.

 

 

문제 핵심

이 문제에서 상어는 가장 가까운 먹이를 먹으러 장소를 이동합니다.

따라서 탐색을 할 때 너비 우선 탐색(BFS)을 이용하는 게 적합한 거 같습니다.

 

저는 이 문제를 해결할 때 두 가지 실수를 하여 시간이 오래 걸렸습니다.

 

실수 1

상어의 위치를 0으로 초기화하지 않았다.

- 초기 입력에서 상어의 위치는 9로 입력되기 때문에 상어의 위치를 0으로 초기화하지 않으면

나중 탐색 때 경우에 따라 해당 칸은 비어있음에도(물고기가 없는 칸) 지나갈 수 없습니다.

=> 상어의 크기가 9 이하인 경우에만 해당됩니다.

 

실수 2

움직임 순서를 (상, 좌, 우, 하) 순서로 정하면 아래의 문제 조건을 보장한다고 착각을 했다.

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

- (상, 좌, 우, 하) 순서의 움직임이 문제의 조건을 보장한다는 착각에 의해 위에서 언급한 문제 조건을 확인하지 않았습니다.

=> 해당 전제는 아래와 같은 반레를 가집니다.

반례 예시

만약 상어가 빨간색 위치에서 처음 먹이 사냥을 시작한다면

다음 위치는 초록색 원이 적합하다.

그러나 위의 전제를 따라가면 파란색 원의 위치로 이동하게 된다.

 

전체 코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())

mat = []

sharkPos = (0, 0)
sharkSize = 2
cntAte = 0

dx = [0, -1, 1, 0]
dy = [-1, 0, 0, 1]

for i in range(N):
    mat.append([])
    row = list(map(int, sys.stdin.readline().strip().split()))

    for j in range(N):
        mat[i].append(row[j])

        if row[j] == 9:
            sharkPos = (i, j)


answer = 0

while True:
    que = deque([( sharkPos[0], sharkPos[1], 0)])
    mat[sharkPos[0]][sharkPos[1]] = 0
    visited = [ [False] * N for _ in range(N) ]
    visited[sharkPos[0]][sharkPos[1]] = True

    isEat = False
    fishPos = (float('inf'), float('inf'))
    toFishDistance = float('inf')

    while que:
        cr, cc, ct = que.popleft()

        for i in range(4):
            if 0 <= cr+dy[i] < N and 0 <= cc+dx[i] < N and ct+1 <= toFishDistance and not visited[cr+dy[i]][cc+dx[i]] and mat[cr+dy[i]][cc+dx[i]] <= sharkSize:
                que.append((cr+dy[i], cc+dx[i], ct+1))
                visited[cr+dy[i]][cc+dx[i]] = True

                if 0 < mat[cr+dy[i]][cc+dx[i]] < sharkSize: # 먹이 후보
                    isThisBest = False
                    isEat = True
                    
                    if cr+dy[i] < fishPos[0]:
                        isThisBest = True
                    
                    elif cr+dy[i] == fishPos[0] and cc+dx[i] < fishPos[1]:
                        isThisBest = True
                        
                    
                    if isThisBest:
                        fishPos = (cr+dy[i], cc+dx[i])
                        toFishDistance = ct+1
                    
    if not isEat:
        break

    else:
        mat[fishPos[0]][fishPos[1]] = 0
        sharkPos = (fishPos[0], fishPos[1])
        answer += toFishDistance
        cntAte += 1

        if sharkSize <= cntAte:
            cntAte = 0
            sharkSize += 1

print(answer)