[python]백준 2589번: 보물섬(BFS)

# 2589 보물섬
https://www.acmicpc.net/problem/2589

2589번: 보물섬

코드

import sys
input = sys.stdin.readline

from collections import deque

r, c = map(int, input().strip().split())
graph = []
for _ in range(c):
  graph.append(list(input()))

# 상하좌우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(i,j):
  queue=deque()
  queue.append((i,j))
  visited = [[0]*c for _ in range(r)]
  visited[i][j] = 1
  cnt = 0

  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= r or ny < 0 or ny >= c:
        continue
      elif graph[nx][ny] == 'L' and visited[nx][ny] == 0:
        visited[nx][ny] = visited[x][y] + 1
        cnt = max(cnt, visited[nx][ny])
        queue.append((nx, ny))
  return cnt-1

result = 0
for i in range(r):
  for j in range(c):
    if graph[i][j] == 'L':
      result = max(result, bfs(i,j))

print(result)

📝 풀이

주어진 보물 지도에서 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 묻혀있다. (0, 0) 부터 (r, c)까지 BFS알고리즘을 사용해 최단거리가 가장 큰 값을 출력해야 한다.

🔓 코드 뜯어보기

import sys
input = sys.stdin.readline

from collections import deque

r, c = map(int, input().strip().split())
graph = []
for _ in range(r):
  graph.append(list(input().strip()))
 
# graph = [
# ['W', 'L', 'L', 'W', 'W', 'W', 'L'],
# ['L', 'L', 'L', 'W', 'L', 'L', 'L'],
# ['L', 'W', 'L', 'W', 'L', 'W', 'W'],
# ['L', 'W', 'L', 'W', 'L', 'L', 'L'],
# ['W', 'L', 'L', 'W', 'L', 'W', 'W'],
# ]

# 상하좌우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

입력값을 빠르게 받기 위해서 import sys를 해주고 input에 sys.stdin.readline을 해준다. bfs를 사용해야 하므로 deque 모듈을 불러오고 r과 c에 입력값을 저장해준다.
지도를 생성하기 위해 graph에 r만큼 반복해 2차원 배열을 생성한다. 가끔 입력값에 /n이 들어올 때가 있어 strip()을 사용해서 값을 제거해주고, 상하좌우 탐색을 위한 dx, dy를 생성해준다.

def bfs(i,j):
  queue=deque() # BFS 알고리즘을 사용하기 위해 deque()를 사용
  queue.append((i,j)) # 시작점 i,j를 queue에 넣어준다.
  visited = [[0]*c for _ in range(r)] # 방문처리 리스트 생성
  visited[i][j] = 1 # 처음 방문하는 좌표 방문처리
  cnt = 0

  while queue:
    x,y = queue.popleft() # 시작점 x, y 부터 탐색 시작
    for i in range(4): # 4방향으로 탐색
      nx = x + dx[i]
      ny = y + dy[i]
      
      # 범위 초과시 무시
      if nx < 0 or nx >= r or ny < 0 or ny >= c:
        continue
      # 탐색한 곳이 길(L)이면서 visited[nx][ny]가 0이라면 방문하지 않은 곳
      elif graph[nx][ny] == 'L' and visited[nx][ny] == 0:
        visited[nx][ny] = visited[x][y] + 1 # 현재 위치(nx, ny) = 직전위치(x, y)까지 걸린시간 + 1
        cnt = max(cnt, visited[nx][ny]) # 현재 cnt값과 위에서 저장한 걸린시간 값 중 큰 것을 cnt에 저장
        queue.append((nx, ny)) # 탐색한 곳(nx,ny) 부터 4방향 탐색을 하기 위해 queue에 nx, ny를 삽입
  return cnt-1

bfs 함수를 생성해서 파라미터에 탐색할 위치인 i, j값을 넣어준다. queue에 탐색할 좌표를 넣어주고 방문처리를 위한 2차원 visited를 생성해준다. 처음 방문하는 visited[i][j]값을 1로 설정해 방문처리를 해준다. 이동한 거리를 카운트 하기위해 cnt를 0으로 설정해준다.

queue.popleft()로 큐에 담긴 위치를 x,y에 저장해주고 4방향으로 탐색한 값을 각각 nx, ny값에 저장시켜준다. 4방향 탐색이기 때문에 nx, ny가 0보다 작거나 r, c보다 크거나 같으면 continue를 통해 무시하도록 해준다.

탐색한 곳이 길(L)이면서 visited[nx][ny]가 0이라면 방문하지 않은 곳이기 때문에 현재 위치(nx, ny)에 직전위치(포함된 시간값) + 1을 해줘서 걸린시간을 갱신해준다. 저장된 cnt와 갱신된 visited[nx][ny]를 비교해 큰 값을 cnt에 저장시켜준다.
그리고 다시 탐색한 곳(nx, ny)부터 4방향 탐색을 하기위해서 queue에 nx, ny값을 넣어준다.

result = 0
for i in range(r):
  for j in range(c):
    if graph[i][j] == 'L':
      result = max(result, bfs(i,j))

print(result)

이중for문으로 전체 지도를 탐색하면서 길(L)을 만날때마다 bfs를 실행시켜줘서 result값과 bfs탐색값 중 큰 것을 result에 계속해서 저장시켜준다. 모든 탐색이 끝나면 두 곳 사이를 최단 거리로 이동하는 시간이 출력된다.