백준 2589번 보물섬 골드5 - Python 풀이

2589번 보물섬 문제는 그래프 너비 우선 탐색(BFS) 와 부루트 포스(Brute Force)를 이용하여 푸는 문제다. 

 

기본적인 풀이 아이디어는

1. 모든 칸에 대해 순회하는데

2. 해당 칸이 육지라면 너비 우선 탐색을 사용하고

3. 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 두 곳 간의 최단 거리를 저장하는데

4. 그 저장한 시간들 중 최대값이 바로 보물이 묻혀있는 두 곳 사이의 최단 거리를 이동하는 시간이다.

라고 정리할 수 있다.

 

다음 코드는 pypy3로 제출하면 통과할 수 있지만 Python3로는 시간초과가 발생한다.

방문 여부를 저장하는 추가 배열을 생성해서 않기 위해 graph 배열에 "L"과 'l' 문자를 번갈아 저장하면서 육지를 구분함과 동시에 flag로 활용했다. (결과적으로 잘못된 접근이였다.)

import sys, collections

input = sys.stdin.readline

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

dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]


def bfs(x: int, y: int, flag: str):
    max_cnt = 0
    que = collections.deque([(x, y, 0)])
    graph[x][y] = flag
    while que:
        x, y, cnt = que.popleft()
        max_cnt = max(max_cnt, cnt)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and graph[nx][ny] != "W"
                and graph[nx][ny] != flag
            ):
                que.append((nx, ny, cnt + 1))
                graph[nx][ny] = flag
    return max_cnt


result = []
flags = ["L", "l"]

for i in range(n):
    for j in range(m):
        if graph[i][j] == flags[0]:
            result.append(bfs(i, j, flags[1]))
        elif graph[i][j] == flags[1]:
            result.append(bfs(i, j, flags[0]))

print(max(result))

visted라는 방문 여부를 저장하는 추가배열을 생성하면서 구하더라도 간단한 아이디어를 통해 Python3로 통과 가능한 로직을 작성할 수 있다.

2번 스텝에서 해당 칸이 육지라면 너비 우선 탐색을 사용하고 =>  해당 칸이 육지면서 끝점이면 너비 우선 탐색을 사용하고 로 조건을 추가한다면 내부 점들은 탐색하지 않기 때문에 탐색 시간을 획기적으로 줄여줄 수 있는 아이디어다.

from collections import deque
import sys

h, w = map(int, input().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y):
    visited = [[-1] * w for _ in range(h)]
    queue = deque([(x, y, 0)])
    visited[x][y] = 0
    while queue:
        x, y, c = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == "L" and visited[nx][ny] == -1:
                    visited[nx][ny] = c + 1
                    queue.append((nx, ny, c + 1))
    return c


result = 0
for x in range(h):
    for y in range(w):
        if 0 < x < h - 1:
            if graph[x - 1][y] == "L" and graph[x + 1][y] == "L":
                continue
        if 0 < y < w - 1:
            if graph[x][y - 1] == "L" and graph[x][y + 1] == "L":
                continue
        if graph[x][y] == "L":
            if result < bfs(x, y):
                result = bfs(x, y)
print(result)

알고리즘 풀이에서 아이디어를 떠올릴 때는 발상적인 아이디어를 떠올리기 보다는 

1. 알고리즘 변경으로 시간 복잡도를 줄이기

2. 더 촘촘한 조건으로 경우의 수 가지치기

3. 중복 연산 제거하기

같은 일반적인 아이디어를 가지고 문제를 풀어나가는게 좋겠다.