[백준-Python] 아기상어2 : 17086번

🥈 Silver2

 

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

 

 

 

✅ 정답풀이

import sys
from collections import deque

input = sys.stdin.readline


m, n = map(int, input().rstrip().split())


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

def bfs():
    result = 0


    while queue:
        cy, cx = queue.popleft()


        for i in range(8):
            ny, nx = dy[i] + cy, dx[i] + cx

            # 상어가 없는 0에 대해 이동 거리 계산
            if 0 <= ny < m and 0 <= nx < n and board[ny][nx] == 0:
                board[ny][nx] = board[cy][cx] + 1
                result = max(result, board[ny][nx])
                queue.append((ny, nx))

    return result


board = [list(map(int, input().strip().split())) for row in range(m)]

queue = deque()

# 아기상어가 위치한 곳(1) 큐에 넣기
for i in range(m):
    for j in range(n):
        if board[i][j] == 1:
            queue.append((i, j))


result = bfs()
print(result - 1)

 

최단거리 문제를 풀때, 방문여부를 위한 리스트를 따로 만들었는데 이번엔 board 자체에 이동거리를 저장하는 식으로 풀이하였다. 

여태 출발점이나 타겟 도착점이 주어지는 경우만 문제를 풀어보다가, 출발점이 정해져있지 않고 상어(1)이 존재하는 곳들의 거리들에 대해 가장 긴 거리값을 구하는 문제였다.

 

1이 위치한 곳에 대한 거리를 구하는문제이기 때문에, 큐에 상어가 위치한 좌표를 넣어주었고, 각 보드 칸에는 가장 가까운 상어 위치를 도달하기 위한 최단거리를 담는다. 

 

 

 

 

 

먼저 큐에 넣은 아기상어의 좌표값을 꺼내 그 좌표 값을 기준으로 8방향으로 순회하면서 방문한적 없는 0인값에 1을 더해 이동거리를 업데이트해준다. 그럼 그림과 같을것이다. 8방향으로 순회를 하면서 board값을 이동거리로 업데이트해주고, 좌표를 큐에 넣어줌으로써 아기상어가 모두 큐에서 나오면 저 그림과 같은 상태에서, 큐에 넣어둔 값을 기준으로 또 1을 더해서 아직 방문하지 않은 0의 좌표들을 채워나가는 방식이다. 

 

 

❗️상어위치를 기준으로 담은 board값(거리)는 0이 아닌 1을 기준으로 이동거리를 담았기 때문에, 거리-1을 해줘야 답을 구할수있다.