[백준] 2589번 보물섬(BFS알고리즘)(Python - 파이썬)

백준 2589번 문제입니다. (solved.ac)기준 골드 5 문제입니다.

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

2589번: 보물섬

보물은 서로 간에 '최단 거리'로 이동하는데 있어 '가장 긴 시간이 걸리는' 육지 두 곳에 나뉘어 묻혀있다고 합니다. 그 보물이 묻혀있는 곳 사이의 최단거리를 구하는 문제입니다. 예제 입력 1  보물은 (3,0)과 (4,1)에 묻혀있습니다.

(0,0) 부터 (n,m)까지 너비우선 탐색(BFS알고리즘)을 사용하여 최단거리가 가장 큰 값을 ans라는 전역변수에 저장하여 마지막에 정답(ans)을 출력하는 방식으로 구현하였습니다. 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())
graph = []

# 전역변수 ans 선언
global ans
ans = 0

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

# graph에 보물지도의 정보 입력
# 바다(W)는 이동 불가 육지(L)로만 이동 가능
for _ in range(n) :
    graph.append(list(sys.stdin.readline().rstrip()))

# 최단거리를 탐색하기 위하여 너비우선 탐색을 사용
def Bfs(x,y) :

    global ans

    #BFS알고리즘을 사용하기 위해 deque()를 사용
    queue = deque()

    # 시작점(x, y)을 queue에 넣어줌
    queue.append((x,y))

    # queue가 빌 때까지 반복
    while queue :

        # 시작점(x,y)부터 탐색 시작
        x, y = queue.popleft()

        # 4방향(상,하,좌,우)으로 탐색
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 초과시 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m :
                continue
            # 탐색한 곳이 바다(W)이면 무시
            if graph[x][y] == "W" :
                continue
            # 탐색한 곳이 길(L)이면서 distance가 -1이라면(-1은 방문하지 않은 곳이라는 뜻)
            if graph[nx][ny] == "L" and distance[nx][ny] == -1 :
                # 현재 탐색한 곳(distance[nx][ny])에
                # 직전 위치까지 걸린 시간(distance[x][y]) + 1
                # 을 해줌으로써 현재 탐색한 곳(distance[nx][ny])까지
                # 걸린 시간 및 방문 처리를 해줄 수 있음.
                distance[nx][ny] = distance[x][y] + 1
                # 탐색한 곳(nx,ny)부터 4방향 탐색을 하기 위해
                # queue에 (nx,ny)를 삽입
                queue.append((nx, ny))
                # 정답(ans)은 탐색한 곳(distance[nx][ny])과
                # 이전의 최댓값(ans)를 비교하여 더 큰 값을 정답(ans)에 담아줌.
                # 최단거리가 가장 긴 곳을 구해야하기 때문
                ans = max(distance[nx][ny], ans)

    return ans





# 그래프의 (0,0)부터 (n,m)까지 탐색
for i in range(n) :
    for j in range(m) :
        # graph[i][j](탐색시작 지점)이 육지(L)이라면 탐색 시작
        if graph[i][j] == "L":
            # 최단거리를 측정할 distance 리스트 생성
            # -1은 방문하지 않았다는 뜻이고 시작점은 0으로 만들어줌.
            # 새로 탐색할 때마다 distance정보를 초기화
            distance = [[-1] * m for _ in range(n)]
            # 탐색 시작점을 0으로 설정
            distance[i][j] = 0
            # 너비우선 탐색 시작(ans값 갱신)
            Bfs(i,j)

print(ans)