백준 16236 아기 상어

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/16236

풀이

난이도 : Gold III

상어의 크기와 필요로 하는 먹이의 수를 따로 변수에 저장하여 관리하였고, 이것들과 비교하여 움직일 수 있는 공간들을 bfs로 탐색하였다.

주의해야할 점은 bfs로 탐색하되 탐색하는 순서가 정해져있다는 것이다. 일단 가장 가까운 거리를 우선적으로 생각해야하고,
거리가 같은 곳이 여러 곳 있다면 1)위, 2)왼쪽을 우선순위로 정해야한다.

처음에는 bfs에서 움직일 때 가장 많이 사용하는 dx와 dy에서 순서만 잘 지켜주면 될 것이라고 생각하였고, 조건에 만족하는 곳을 만나면 바로 return해주는 방법으로 코드를 구현하였는데, 이럴 경우 틀린답이 나오게 된다.

👉 그래서 조건에 만족하는 곳이 나오게 되면 그때부터는 q에 남은 공간에 대해서만 탐색을 진행하고, 조건에 만족하는 값들 중
거리가 가까운 순으로 만족하는 x, y값을 구하였다.

코드

from collections import deque

n = int(input())

array = []

for _ in range(n):
    array.append(list(map(int, input().split())))

x, y = 0, 0
for i in range(n):
    for j in range(n):
        if array[i][j] == 9:
            x = i
            y = j
            array[i][j] = 0

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

def bfs(x, y):
    global size

    q = deque()
    q.append([x, y, 0])

    visited = [[False] * n for _ in range(n)]
    visited[x][y] = True
    results = []

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if visited[nx][ny] or array[nx][ny] > size:
                continue
            if array[nx][ny] < size and array[nx][ny] != 0:
                results.append([nx, ny, count+1])
                continue
            
            if len(results) != 0:
                continue

            visited[nx][ny] = True
            q.append([nx, ny, count+1])

    if len(results) == 0:
        return -1, -1, 0
    else:
        results.sort(key=lambda x: (x[2], x[0], x[1]))
        return results[0][0], results[0][1], results[0][2]

size, need = 2, 2
result = 0
while True:
    x, y, count = bfs(x, y)
    if x == -1 and y == -1:
        break
    else:
        array[x][y] = 0
        result += count
        need -= 1
        if need == 0:
            size += 1
            need = size

print(result)