[백준/BOJ] - 2589번 python 풀이 - BFS

---

Key Point

1. 각 case 마다 visited의 초기값을 사용해야하기 때문에 bfs 접근할 때 마다 deepcopy 해준다.

2. 시작점의 visited 값은 1로 설정해준다.( 0으로 설정할 경우 시작점으로 다시 되돌아갈 수 있기 때문이다.)

---

import sys
import copy
input = sys.stdin.readline
from collections import deque

n, m = map(int,input().split())
mapp = [list(map(str, input().rstrip())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
res = 0
final = 0
def bfs(i,j):
    global res
    #bfs 들어올 때 마다 visited의 초기 값을 사용해야함
    temp_visited = copy.deepcopy(visited)
    #기준 값의 visited 값을 1로 만들어준다.(※ visited값이 0인 값으로 이동할 것이기 때문에)
    #해당값을 1로 만들지 않고 0으로 냅두면 시작점으로 다시 되돌아갈 수 있음(나중에 -1 해주면된다)
    temp_visited[i][j] = 1
    while queue:
        a,b = queue.popleft()
        for i in range(4):
            rx = a + dx[i]
            ry = b + dy[i]
            if 0<=rx<n and 0<=ry<m:
                if mapp[rx][ry] == 'L' and temp_visited[rx][ry] == 0:
                    queue.append((rx,ry))
                    temp_visited[rx][ry] = temp_visited[a][b] + 1
                    #case 마다 res의 최댓값을 산출한다.
                    res = max(res, temp_visited[rx][ry])


queue = deque()
for i in range(n):
    for j in range(m):
        if mapp[i][j] == 'L':
            queue.append((i,j))
            bfs(i,j)
#2중 for문을 모두 돌린 후 -1한 값 출력.(시작값을 1로 했기 때문에)
print(res-1)