[백준/삼성] 16236 아기상어

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

16236번: 아기 상어

 

유형 : BFS/ DFS (나는 BFS로 풀었당)

어려웠던 부분은 '최단 거리'를 어떻게 구하냐는 것이다. BFS로 최단거리를 구하는 방법을 꼭 기억해두자 !!

 

현재 위치 (x, y)에서 ->

상하좌우 를 확인하는데 (for 문으로 확인 nx = x + dx[i], ny = y + dy[i])->

0 ~ n 의 범위 안에 있어야 하며 (0 <=nx < n and 0 <= ny < n) ->

아직 방문되지 않았다면 (dist[nx][ny] == -1) -> 

dist[nx][ny] = dist[x][y] + 1

 

한 지점 (상어의 위치) 에서 다른 모든 칸들에 도달하는 '최단 거리' 테이블을 구한다. 

도달 할 수 있는 칸에 있는 '물고기' 들 중에서 자기자신보다 작은 사이즈이며, 가장 가까이에 있는 물고기를 먹을 수 있다. 

이 가장 가까이에 있는 물고기를 어떻게 구해야 할지가 어려웠는데, -> 최단 거리 테이블을 구한 다음에, 하나씩 조건에 맞게 값을 걸러낸 다음 가장 작은 값과 현재 위치의 최단거리를 비교해서 min_dist에 저장한다. 

# 아기 상어
from collections import deque

n = int(input())
size = 2 # 현재 상어의 크기
result = 0
array = []
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

sx, sy = 0, 0 # shark position

for i in range(n):
    for j in range(n):
        if array[i][j] == 9: # 상어 위치
            sx = i
            sy = j
            array[i][j] = 0

def distance(): # 최단 거리 계산
    dist = [[-1]*n for _ in range(n)] # 최단 거리 테이블
    q = deque()
    q.append((sx, sy))
    dist[sx][sy] = 0 # 시작 지점은 최단거리 0 이라고 한다
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1 and array[nx][ny] <= size: # 지나갈 수 있는가 확인
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist


def find(dist): # 최단 거리가 주어졌을 때 먹을 물고기를 찾는 함수
    x, y = 0, 0
    min_dist = INF

    for i in range(n):
        for j in range(n):
            if dist[i][j] != -1 and 1 <= array[i][j] < size: # 먹을 수 있는 물고기인지 확인
                if min_dist > dist[i][j]:
                    min_dist = dist[i][j]
                    x, y = i, j
    if min_dist == INF:
        return None # 먹을 수 있는 물고기가 없다
    return x, y, min_dist

eat = 0 # 지금 먹은 물고기 개수
while True:
    data = find(distance())
    if data == None:
        print(result)
        break
    else:
        result += data[2] # min_dist 만큼 물고기에 도달하는데 시간이 걸릴 것이므로
        sx, sy = data[0], data[1] # 새로운 위치로 이동
        array[sx][sy] = 0 # 먹었으면 0 으로 바꿔준다.
        eat += 1
        if eat >= size:
            size += 1
            eat = 0