[Python][백준] 16236번 아기 상어

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

공부 날짜 : 2022.09.15
정답 참조 여부 : X

아기상어가 먹이를 찾아 이동할때 먹이를 못먹게 될때까지 시간을 구하는 문제이다.

---

bfs기법을 사용해서 상어의 위치로부터 거리에 따라 점점 확산해가며 같은 최소거리에있는 물고기를 찾았다.
그 후 찾은 물고기에 대해 가장 최상측 최좌측 물고기를 찾기위해 정렬을 하고 정렬된 물고기의 첫번째 물고기를 향해 이동했다.(x,y가 최소가됨)
이동후 저장된 distance만큼 시간을 더해주고 해당위치의 물고기를 제거하고 조건들을 초기화 한뒤 bfs를 반복하도록 코드를 설계했다.

---

정답 과정이 조금 특이한데
초기 코드 > 시간초과
시간초과를 수정하기 위한 코드수정 > 무한루프
무한루프 픽스 > 틀렸습니다.
무한루프를 초기코드에서 수정 > 맞췄습니다.

초기 코드의 시간초과가 무한루프에 의한 초과인데 코드이상으로 생각해서 코드를 수정했다가
후에 무한루프 원인을 찾았고 초기코드의 무한루프를 해결했더니 정답이 나왔다.

즉 중간에 수정된 코드에서 뭐가 틀렸는지를 모르겠다....

소스코드

import sys
input = sys.stdin.readline

n = int(input())

#바다의 상황 전체를 저장하는 리스트
sea = []
shark_size = 2
#상어의 동선을 나타내는 리스트
shark_move = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n):
        if a[j] == 9:
            a[j] = 0
            shark_postion = [i,j]
            shark_move[i][j] = 1
    sea.append(a[:])

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

find = [(shark_postion[0],shark_postion[1],0)]
target = []
time = 0
eat_fish_count = 0

while find:
    x,y,distance = find.pop(0)
    
    #최소거리에 있고 먹을수있는 물고기들을 모두 찾았을때
    if len(target) != 0 and target[0][2] == distance:
        #같은 거리에있는 물고기중 최상단 최좌측을 찾기위한 정렬
        target.sort()
        #거리만큼 시간 추가
        time += target[0][2]
        #상어 이동
        shark_postion = [target[0][0],target[0][1]]
        #물고기 제거
        sea[target[0][0]][target[0][1]] = 0
        
        #find리스트 초기화
        find = [(shark_postion[0],shark_postion[1],0)]
        #상어 동선 초기화
        shark_move = [[0 for _ in range(n)] for _ in range(n)]
        #타겟 초기화
        target = []
        
        #먹은 물고기 개수 +1
        eat_fish_count += 1
        #먹은 개수가 상어크기와 같으면 사이즈 증가, 먹은개수 초기화
        if eat_fish_count == shark_size:
            shark_size += 1
            eat_fish_count = 0
            
        continue
        
        

    distance += 1
    for dir in range(4):
        nx = x + dx[dir]
        ny = y + dy[dir]
        
        #범위 이내이고 방문한적 없는 칸이라면
        if 0 <= nx < n and 0 <= ny < n and shark_move[nx][ny] == 0:
            
            #빈칸or몸집크기가 같은 물고기일때
            if sea[nx][ny] == 0 or sea[nx][ny] == shark_size:
                find.append((nx,ny,distance))
                shark_move[nx][ny] = 1
                
            #자기보다 작은 물고기 일때
            elif 0 < sea[nx][ny] < shark_size :
                find.append((nx,ny,distance))
                target.append((nx,ny,distance))
                shark_move[nx][ny] = 1
                

print(time)   

pypy3에서 제출해서 정답이 나왔습니다. python3환경에서 정답일지는 모릅니다.