[DFS/BFS/완전탐색] 2589번 - 보물섬(BFS)

[백준] 2589번 - 보물섬

풀이 시간: 20분 이내

 

1) 문제 해결 아이디어

이 문제는 보물이 묻혀있는 두 곳 간의 최단 거리로 이동하는 시간을 문제로 BFS로 풀이가 가능하다.

일단 보물은 육지에 묻혀있을 수 있기 때문에 for문을 돌려 육지인 모든 칸에 대해서 bfs()를 호출하여 모든 경우를 검사해보아야 한다. 여기서 보물은 최단 거리로 이동한다고 가정했을 때 가장 오랜 시간이 걸리는 곳이어야 한다. 그러므로 하나의 보물이 시작점에 있다고 보면 다른 보물은 시작점에서 bfs를 했을 때 기록된 visited의 값 중 최댓값에 위치해야 한다. 두 보물 사이의 최단 거리는 (최댓값 - 1) 이므로 이 값을 리턴하고 종료한다. 그렇게 모든 육지 칸에 대해 bfs를 돌려 얻은 값들 중 최댓값이 이 문제의 정답이 된다. 

 

첫번째 오류. 시간 초과

PyPy3로 제출하면 시간 초과 문제가 해결된다. Python3으로 제출한 코드가 계속 시간 초과가 떴을 때  PyPy3로 제출하면 해결되는 경우도 많다!! 

 

2) 소스코드

from collections import deque

# BFS 
def bfs(x, y):
  visited = [[0] * m for _ in range(n)]
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, y))
  visited[x][y] = 1

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if(0 <= nx < n and 0 <= ny < m):
        # 육지이고 방문하지 않은 곳이면 삽입, 방문 처리
        if(graph[nx][ny] == 'L' and visited[nx][ny] == 0):
          queue.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1
  return max(map(max, visited)) - 1  # 최단 거리

n, m = map(int, input().split())  # 세로, 가로
# L: 육지, W: 바다 
graph = [list(input()) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

min_time = 0
for i in range(n):
  for j in range(m):
    # 육지이면
    if(graph[i][j] == 'L'):
      min_time = max(bfs(i, j), min_time)
print(min_time)