백준 문제 풀이 - 보물섬 2589번

📜 문제 이해하기

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.
보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

💡 문제 재정의

가장 긴 L들의 거리를 출력하라.

✏️ 계획 수립

BFS로 해당 L에서 다른 L까지의 거리를 구할 수 있고 가장 최대 길이가 되는 값을 저장한다. 이 과정을 모든 L에서 반복한다음 최대 길이를 출력한다.

💻 계획 수행

import sys
from collections import deque

if __name__ == '__main__':
    height, width = map(int, sys.stdin.readline().split())
    treasure_map = []
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    for _ in range(height):
        treasure_map.append(list(sys.stdin.readline().strip()))

    max_distance = 0
    for y, row in enumerate(treasure_map):
        for x, element in enumerate(row):
            if element == "L":
                visited = [[0 for _ in range(width)] for _ in range(height)]
                open_set = deque()
                open_set.append((0, y, x))
                visited[y][x] = 1

                while open_set:
                    cur_element = open_set.popleft()
                    cur_distance = cur_element[0]
                    cur_y = cur_element[1]
                    cur_x = cur_element[2]

                    max_distance = max(max_distance, cur_distance)

                    for d in direction:
                        next_y = d[0] + cur_y
                        next_x = d[1] + cur_x
                        if 0 <= next_y < height and 0 <= next_x < width:
                            if treasure_map[next_y][next_x] == "L" and not visited[next_y][next_x]:
                                visited[next_y][next_x] = 1
                                open_set.append((cur_distance + 1, next_y, next_x))

    print(max_distance)

🤔 회고

visited를 cur_y와 cur_x에서 처음에 설정해주었지만 next_y, next_x에서 설정해줘야 다음 탐색때 같은 점을 찾지 않았다. 이와 같은 문제에서 시간 초과와 메모리 초과가 발생한다면 visited 설정을 위와 같이 해야 한다.