[백준 알고리즘] 2589. 보물섬 _ 파이썬

 

 

육지 "L"인 지점을 찾아서 BFS를 사용하여 최장 거리를 저장하는 방식으로 풀었다.

 

 

처음에는 모든 L의 지점을 다 찾아서 돌리니 시간초과가 걸려 시작지점을 줄이는 방법이 없을까 고민을 했다.

 

 

생각해보니 L들에게 둘러쌓여 있는 지점은 최장거리가 될 수 없다는 것을 깨달아, 인접한 L이 2개 이하일 때만

 

시작지점을 넣어서 돌리니 통과했다. 

 

이 때 인접한 L이 1이하라고 조건을 바꾸면 안될까? 라는 생각도 했었는데 W가 없는 지도일 경우, L의 인접지점은 최소 2가 된다.

 

반례

3 2

LL

LL

LL

 

 

import sys
from collections import deque

n, m = map(int, (sys.stdin.readline().split()))
map = []
ans = 0
for _ in range(n):
    map.append(sys.stdin.readline())

start = []

# L과 인접해 있는 면이 2면이하 일때 시작점으로 넣음
for i in range(n):
    for j in range(m):
        cnt = 0
        if map[i][j] == "L":
            if i+1 < n and map[i + 1][j] == 'L': cnt += 1
            if 0 <= i-1 and  map[i - 1][j] == 'L': cnt += 1
            if j+1 < m and map[i][j + 1] == 'L': cnt += 1
            if 0 <= j-1 and map[i][j - 1] == 'L': cnt += 1
            if cnt < 3:
                start.append((i, j))



# BFS 이용하여 가장 먼 위치에서 최단 거리 찾아내기
Q = deque()
for k in range(len(start)):
    sr, sc = start[k][0], start[k][1]
    distance = [[-1] * m for _ in range(n)]
    Q.append((sr, sc))
    distance[sr][sc] = 0
    while Q:
        r, c = Q.popleft()
        if 0 <= r-1 and distance[r-1][c] == -1 and map[r-1][c] == 'L':
            Q.append((r-1, c))
            distance[r-1][c] = distance[r][c] + 1
        if r+1 < n and distance[r+1][c] == -1 and map[r+1][c] == 'L':
            Q.append((r+1, c))
            distance[r+1][c] = distance[r][c] + 1
        if 0 <= c-1 and distance[r][c-1] == -1 and map[r][c-1] == 'L':
            Q.append((r, c-1))
            distance[r][c-1] = distance[r][c] + 1
        if c+1 < m and distance[r][c+1] == -1 and map[r][c+1] == 'L':
                    Q.append((r, c+1))
                    distance[r][c+1] = distance[r][c] + 1
        if len(Q) == 0:
            if distance[r][c] > ans:
                ans = distance[r][c]

print(ans)