[백준 16236] 아기상어 Python

조건대로만 풀었는데 정말 많은 실패를 겪었다... 심지어 6개월 전에 포기했다가 재도전하였던,, 그런 문제였다

상어가 먹을 수 있는 물고기까지의 최단거리를 측정하는 것이기 때문에 BFS를 사용한다. 그래서 bfs 메소드에서는 큐를 이용하여 bfs로직을 수행한다.

validate 메소드에서는 이동할 좌표가 matrix 안에 있는지를 판단한다. [-1, 0] 과 같이 존재하지 않는 좌표는 False를 리턴한다.

bfs를 시작할 때 visit 배열을 만든다. 이 배열은 이미 탐색했던 장소를 표시한다. 그러므로 현재 상어가 있는 곳의 좌표를 표시하고 넘어가는데 이때 현재 상어가 있는 곳이 1로 표시하고 다음 탐색 좌표는 2가 되는 형식이다. 그래서 visit 배열에 매겨지는 숫자는 아기상어가 해당 좌표까지 이동한 거리가 된다. 정확하게는 -1을 해주어야한다. 시작이 1부터이기 때문에!!

현재 상어의 좌표를 큐에 담는다. 그리고 queue가 빌 때까지 bfs를 탐색한다. 이 때 상어가 먹을 수 있는 물고기들은 cand 배열에 담는다.
cand 배열은 [[거리, x좌표, y좌표]]로 구성된다.

최종적으로 bfs가 끝나면 cand배열안에 먹을 수 있는 물고기들이 담겨져 있다. 그래서 거리순, x좌표순, y좌표순 으로 오름차순 정렬하여 반환한다.

반환된 배열에서 제일 앞에 있는 녀석이 아기상어가 먹을 녀석이다. 만약 배열이 비어있다면 먹을 물고기가 없으므로 종료한다. 그리고 물고기를 하나 먹어치우면 eat를 +1 하고 eat == 상어의 사이즈와 같아지면 사이즈를 +1 하고 eat를 0으로 만들어주는 식으로 로직을 작성하였다.

코드는 다음과 같다. 사실 말로만 설명하기에는 불충분하지만 bfs의 기본적인 작동방식을 이해하고 있다면 위에 적혀있는 말만 읽어도 풀 수 있을 것이라고 생각한다!!

import sys
from collections import deque
r = sys.stdin.readline

N = int(r().strip())
matrix = []

for i in range(N):
    matrix.append(list(map(int, r().split(" "))))


X, Y, size = 0, 0, 2
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 9:
            X = i
            Y = j

move = [[0, -1], [1, 0], [0, 1], [-1, 0]]
def validate(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    return True
def bfs(x, y):
    global move, size
    visit = [[0] * N for col in range(N)]
    visit[x][y] = 1
    queue = deque([[x, y]])
    cand = []

    while queue:
        tx, ty = queue.popleft()
        for j in move:
            nx = tx + j[0]
            ny = ty + j[1]
            if validate(nx, ny) and visit[nx][ny] == 0:
                if matrix[x][y] > matrix[nx][ny] and matrix[nx][ny] != 0:
                    visit[nx][ny] = visit[tx][ty] + 1
                    cand.append((visit[nx][ny] - 1, nx, ny))
                elif matrix[x][y] == matrix[nx][ny]:
                    visit[nx][ny] = visit[tx][ty] + 1
                    queue.append([nx, ny])
                elif matrix[nx][ny] == 0:
                    visit[nx][ny] = visit[tx][ty] + 1
                    queue.append([nx, ny])

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

answer = 0
eat = 0
while True:
    matrix[X][Y] = size
    temp = deque(bfs(X, Y))

    if not temp:
        break

    dist, mx, my = temp.popleft()
    answer += dist

    matrix[X][Y] = 0
    X = mx
    Y = my
    eat += 1
    if eat == size:
        eat = 0
        size += 1

print(answer)