[ 알고리즘 ] 아기상어 - bfs

문제

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

16236번: 아기 상어

 

풀이 팁

1. 처음에 작성한 코드는 먹을 수 있는 물고기들을 매번 구하면서 가장 가까우며, 혹은 가장 위 / 가장 왼쪽 기준으로 선택하여 한번에 거리들을 구하는 방식으로 갔다.. ( 아직도 왜 틀린지를 모르겠지만, 계속 틀려서 수정 -> 아시는 분은 댓글 부탁드려요 ㅠ )
https://www.acmicpc.net/board/view/139274

글 읽기 - 왜 틀렸을까요??

 

2. 결국 방문자 처리와 거리를 하나씩 더해가는 식의 방식으로 구현을 했다.

코드

import sys
from collections import deque

n = int(input())
arr = [
    list(map(int,input().split()))
    for _ in range(n)
]

cnt ,time, size = 0, 0, 2 

dxs,dys =[-1,0,1,0], [0,-1,0,1]

visited = [
    [False for _ in range(n)]
    for _ in range(n)
]

cur_x, cur_y = 0,0
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            arr[i][j] = 0
            cur_x, cur_y = i,j

def in_range(x,y):
    return 0<=x<n and 0<=y<n

def init_visited():
    for i in range(n):
        for j in range(n):
            visited[i][j] = False

def can_go(x,y):
    return in_range(x,y) and arr[x][y] <= size and not visited[x][y]

def can_eat(x,y):
    return arr[x][y] != 0 and arr[x][y] < size

def bfs():
    global cur_x, cur_y, size

    dist = [
        [0 for _ in range(n)]
        for _ in range(n)
    ]

    init_visited()

    q = deque()
    q.append((cur_x, cur_y))

    visited[cur_x][cur_y] = True
    eat_fishes = []

    while q:
        x,y = q.popleft()

        for dx,dy in zip(dxs, dys):
            nx,ny = x +dx , y +dy

            if can_go(nx,ny):
                visited[nx][ny] = True
                q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1

                if can_eat(nx,ny):
                    eat_fishes.append((nx,ny, dist[nx][ny]))

    return sorted(eat_fishes, key=lambda x : (-x[2],-x[0],-x[1]))

while True:
    ate_fishes = bfs()

    if len(ate_fishes) == 0:
        break

    next_x,next_y,distance = ate_fishes.pop()

    time += distance
    arr[next_x][next_y] = 0

    cur_x,cur_y = next_x,next_y
    cnt += 1
    
    if cnt >= size:
        size += 1
        cnt = 0

print(time)