boj.kr/16236 아기 상어 (gold3) 파이썬 풀이

1. 아기상어 최초 위치 찾기

2 먹을 수 있는 상어가 없을 때가지 아래를 반복

3. bfs 방식으로 현재 아기상어 크기로 먹을 수 있는 상어 리스트 찾기

4. bfs 방식으로 찾은 먹은 상어 리스트를 거리 오름차순, 위, 왼쪽 순으로 정렬

5. 상어 먹은 cnt를 1 증가하고 현재 아기 상어 사이즈와 같으면 아기 상어 사이즈를 1 증가

6. 먹은 상어 리스트의 첫번째 상어 좌표의 값을 0으로 저장

7. 먹은 상어 리스트의 첫번째 상어까지 거리를 ans 값에 더하기

8. 먹은 상어 리스트의 크기가 0이면 ans 값을 출력

 

bfs 내부에서 대부분 처리하려고 풀이한 결과 일부 테스트 케이스에서만 통과했다. 정답 풀이 참고해 위 순서로 풀이해 성공했다.

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
shark_size = 2
shark_eat_cnt = 0

from collections import deque

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)

def bfs(y, x):
    chk = [[0] * N for _ in range(N)]
    global shark_size
    dq = deque()
    dq.append((y, x))
    eat_list = []

    while dq:
        (y, x) = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<N and 0<=nx<N and board[ny][nx]<=shark_size and chk[ny][nx] == 0:
                chk[ny][nx] = chk[y][x] + 1
                dq.append((ny, nx))
                if 0 < board[ny][nx] < shark_size:
                    eat_list.append((ny, nx, chk[ny][nx]))

    eat_list.sort(key=lambda x: (x[2], x[0], x[1]))
    return eat_list


ans = 0
def eat_shark():
    for y in range(N):
        for x in range(N):
            if board[y][x] == 9:
                ny = y
                nx = x
                board[y][x] = 0
    while True:
        global ans
        global shark_eat_cnt
        global shark_size

        eat_list = bfs(ny, nx)

        if len(eat_list) == 0:
            break
        else:
            (ny, nx, distance) = eat_list[0]

            shark_eat_cnt += 1
            if shark_size == shark_eat_cnt:
                shark_size += 1
                shark_eat_cnt = 0

            board[ny][nx] = 0
            ans += distance

    return ans

print(eat_shark())

bfs를 여러번 돌린다고 무조건 시간초과 나지 않는다. 문제 조건을 보고 bfs 내부에서 해결되지 않는 조건을 순서대로 처리한다.

 

 

[ 위 풀이를 더 간소화한 코드 ]

1. 아기상어 위치 찾기

2. 아기상어가 먹을 수 있는 물고기가 없을 때까지 아래를 반복

2.1. 아기상어의 좌표를 방문체크

2.2. 아기상어의 좌표값을 0으로 갱신

2.3. bfs 방식으로 아기상어가 먹을 수 있는 물고기의 좌표와 그 좌표까지의 최단거리를 fishes에 저장

2.4. fishes를 거리, y좌표, x좌표 오름차순으로 정렬

2.5. fishes의 0번째 fish의 최단거리만큼 소요시간 변수에 증감하고 아기 상어의 좌표를 fish 좌표로 갱신

2.6. 아기상어가 먹은 물고기 개수를 증감하고 아기상어의 크기만큼 먹었으면 크기를 1증감 및 물고기 개수를 0으로 갱신

2.7. fishes를 빈 배열로 갱신

3 소요시간 변수값을 출력

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
for y in range(N):
    for x in range(N):
        if graph[y][x] == 9:
            (sy, sx) = (y, x)

dy = (0, 0, -1, 1)
dx = (-1, 1, 0, 0)
from collections import deque
fishes = []
def set_fishes(py, px):
    dq = deque()
    dq.append((py, px, 0))
    while dq:
        (y, x, d) = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<N and 0<=nx<N and visited[ny][nx] == 0:
                visited[ny][nx] += 1
                if graph[ny][nx] == 0 or graph[ny][nx] == shark_size:
                    dq.append((ny, nx, d+1))
                elif graph[ny][nx] < shark_size:
                    fishes.append((ny, nx, d+1))
    fishes.sort(key = lambda x: (x[2], x[0], x[1]))

sec = 0
shark_size = 2
eat_cnt = 0
while True:
    visited = [[0] * N for _ in range(N)]
    visited[sy][sx] += 1
    graph[sy][sx] = 0
    set_fishes(sy, sx)
    if len(fishes) == 0:
        break
    else:
        sec += fishes[0][2]
        sy = fishes[0][0]
        sx = fishes[0][1]
        eat_cnt += 1
        if eat_cnt == shark_size:
            shark_size += 1
            eat_cnt = 0
        fishes = []
print(sec)

bfs방식을 사용하는 이유는 먹을 수 있는 물고기 좌표까지의 최단거리를 함께 저장하기 위함이다.