🥚문제링크

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

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색

---

🍳코드

PyPy3로 통과, Python3는 시간초과

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

n, m = map(int, input().split())
arr = [list(input()) for _ in range(n)]

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]


def bfs(r, c):
    q = deque([(r, c)])
    # tmp_dist[r][c] == -1이면 방문 X
    tmp_dist = [[-1]*m for _ in range(n)]
    tmp_dist[r][c] = 0

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < n and 0 <= nc < m:
                if arr[nr][nc] == 'L' and tmp_dist[nr][nc] == -1:
                    q.append((nr, nc))
                    tmp_dist[nr][nc] = tmp_dist[r][c] + 1
                    dist[nr][nc] = max(dist[nr][nc], tmp_dist[nr][nc])

# dist[r][c] = (r, c)의 최단거리 중 가장 큰 값
dist = [[-1]*m for _ in range(n)]
for r in range(n):
    for c in range(m):
        if arr[r][c] == 'L':
            bfs(r, c)

print(max(map(max, dist)))

---

🧂아이디어

BFS

1. 세로의 크기 n, 가로의 크기 m, 보물지도 arr를 입력받는다.

2. 2차원 리스트 dist를 만든다.
   (dist[r][c] = (r, c)까지의 최단거리 중 가장 큰 값)

3. arr을 순회하며 arr[r][c] == 'L'인 모든 좌표 (r, c)에 대해 함수 bfs를 실행한다.

4. bfs함수 내부에서는 tmp_dist라는 2차원 리스트를 통해 방문 표시 및 인자로 넘겨준 (r, c)에서 방문할 수 있는 모든 좌표들까지의 최단거리를 저장한다.

5. 임의의 좌표 (x, y)에 대하여 tmp_dist[x][y]에 저장된 최단거리가 dist[x][y]에 저장된 최단거리보다 크다면 dist[x][y]의 값을 tmp_dist[x][y]의 값으로 갱신텍스트한다.

6. dist에서의 최대값을 출력한 것이 문제에서 원하는 답이다.
   (최단 거리로 이동하는데 있어 가장 긴 시간 = 최단거리 중 가장 긴 거리)