[ProblemSolving] 백준 2589번 보물섬 문제풀이

백준 2589번 BFS 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시면 됩니다.

 

백준 2589번 보물섬 문제 해설

2589번: 보물섬

보물이 있는 위치는 서로 간에 최단 거리로 이동했을 때 가장 이동 시간이 긴 육지 2곳에 있습니다. 가장 긴 이동 시간을 가진 육지를 찾는 방법은 각각의 육지에서 다른 육지로의 거리들을 비교하여 최댓값을 저장하는 방식을 활용하면 될 것입니다. 따라서 해당 문제는 브루트 포스와 너비 우선 탐색을 이용하여 해결할 수 있습니다. 해결 방법은 다음과 같습니다.

 

1. "L"이 있는 위치를 검색한다.
2. 해당 위치에서 너비 우선 탐색을 실시하여 가장 큰 이동 시간을 저장한다.
3. 각각의 변수를 초기화시켜준 후에 1번의 과정을 반복한다.
4. 각각의 "L"에서 저장된 이동 시간 중에 가장 큰 값을 출력한다.

위의 과정을 코드로 표현하면 다음과 같습니다.

 

from collections import deque
 
def initDistance():
  for i in range(n):
    for j in range(m):
      distance[i][j] = 0
      visited[i][j] = False
 
 
def bfs(x, y):
  queue = deque()
  queue.append((x,y))
  visited[x][y] = True
  count = 0
  dx = [-1, 0, 1, 0]
  dy = [0, -1, 0, 1]
 
  while queue:
    x, y = queue.popleft()
 
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx >= 0 and nx < n and ny >= 0 and ny < m:
        if not visited[nx][ny] and data[nx][ny] == "L":
          distance[nx][ny] = distance[x][y] + 1
          count = max(count, distance[nx][ny])
          queue.append((nx, ny))
          visited[nx][ny] = True
  return count
 
n, m = map(int,input().split())
 
data = []
maxDistance = []
distance = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
for _ in range(n):
  data.append(list(str(input())))
 
for i in range(n):
  for j in range(m):
    if data[i][j] == "L":
      initDistance()
      maxDistance.append(bfs(i,j))
 
print(max(maxDistance))
 

 

각각의 "L"에서 다른 "L"로의 이동 시간을 계산하고, 최댓값을 count에 저장해줍니다. 계산이 종료되면 count값을 반환해주고, 해당 값을 maxDIstance에 저장합니다. 모든 "L"에 대하여 계산이 완료되었으면 maxDistance에서 가장 큰 값을 출력해줍니다.