[Python] 백준 - 2589 보물섬

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/2589

---

시간 초과 풀이

from sys import stdin
from collections import deque


def bfs(start_r, start_c):
    queue = deque()
    queue.append((start_r, start_c))
    visited = [[-1] * max_c for _ in range(max_r)]
    visited[start_r][start_c] = 0

    while queue:
        r, c = queue.popleft()

        if r > 0 and treasure[r - 1][c] == 'L' \
        and visited[r - 1][c] == -1:
            visited[r - 1][c] = visited[r][c] + 1
            queue.append((r - 1, c))

        if c > 0 and treasure[r][c - 1] == 'L' \
        and visited[r][c - 1] == -1:
            visited[r][c - 1] = visited[r][c] + 1
            queue.append((r, c - 1))

        if r < (max_r - 1) and treasure[r + 1][c] == 'L' \
        and visited[r + 1][c] == -1:
            visited[r + 1][c] = visited[r][c] + 1
            queue.append((r + 1, c))

        if c < (max_c - 1) and treasure[r][c + 1] == 'L' \
        and visited[r][c + 1] == -1:
            visited[r][c + 1] = visited[r][c] + 1
            queue.append((r, c + 1))

    return visited[r][c]


max_r, max_c = map(int, stdin.readline().split())
max_value = 0
treasure = []

for _ in range(max_r):
    treasure.append(list(stdin.readline().rstrip()))

for i in range(max_r):
    for j in range(max_c):
        if treasure[i][j] == 'L':
            max_value = max(max_value, bfs(i, j))

print(max_value)

최단 거리를 구하는 문제이므로 BFS로 구현했다. 모든 'L'인 지점에 대하여, 그 지점에서 갈 수 있는 가장 먼 곳의 최단 거리를 구하고, 그 거리들 중 가장 큰 값을 구했다. 그런데 시간 초과가 떴다.

1987번 문제처럼, PyPy3으로는 통과가 되었다.

문제 해결 과정

    if r > 0 and treasure[r - 1][c] == 'L' \
    and visited[r - 1][c] == -1:
        visited[r - 1][c] = visited[r][c] + 1
        queue.append((r - 1, c))

위 코드의 조건문 부분은 3가지 조건으로 이루어져 있다.

① r > 0 (인덱스 검사)
② treasure[r - 1][c] == 'L' (위쪽 땅이 'L'인지 확인)
③ visited[r - 1][c] == -1 (위쪽 땅을 아직 방문하지 않았는지 확인)

1번 이전에 2번, 3번이 먼저 나오면 인덱스 오류가 발생할 수 있다. 따라서 1번이 먼저 나오는 것은 바꿀 수 없다.

2번과 3번 중에는 무엇이 먼저 나오는 것이 좋을까? 맵에 따라 다르겠지만, 'L'의 비율이 높은 맵인 경우에는 뒤로 갈수록 방문했던 곳을 다시 검사하는 경우가 많아질 것이다. 그래서 3번 조건을 2번 조건보다 먼저 검사하도록 코드를 수정한 뒤 다시 제출했더니 통과했다.

최종 풀이

from sys import stdin
from collections import deque


def bfs(start_r, start_c):
    queue = deque()
    queue.append((start_r, start_c))
    visited = [[-1] * max_c for _ in range(max_r)]
    visited[start_r][start_c] = 0

    while queue:
        r, c = queue.popleft()

        # 방문 여부를 먼저 검사하고, 그 뒤에 땅이 육지인지를 검사한다.
        if r > 0 and visited[r - 1][c] == -1 \
        and treasure[r - 1][c] == 'L':
            visited[r - 1][c] = visited[r][c] + 1
            queue.append((r - 1, c))

        if c > 0 and visited[r][c - 1] == -1 \
        and treasure[r][c - 1] == 'L':
            visited[r][c - 1] = visited[r][c] + 1
            queue.append((r, c - 1))

        if r < (max_r - 1) and visited[r + 1][c] == -1 \
        and treasure[r + 1][c] == 'L':
            visited[r + 1][c] = visited[r][c] + 1
            queue.append((r + 1, c))

        if c < (max_c - 1) and visited[r][c + 1] == -1 \
        and treasure[r][c + 1] == 'L':
            visited[r][c + 1] = visited[r][c] + 1
            queue.append((r, c + 1))

    return visited[r][c]


max_r, max_c = map(int, stdin.readline().split())
max_value = 0
treasure = []

for _ in range(max_r):
    treasure.append(list(stdin.readline().rstrip()))

for i in range(max_r):
    for j in range(max_c):
        if treasure[i][j] == 'L':
            max_value = max(max_value, bfs(i, j))

print(max_value)