[백준] 2589번 보물섬 (Python)

백준 2589 보물섬

BFS를 활용해서 풀었지만, BFS가 중요한 문제는 아니었다. 가장 먼 지점을 찾는 것이 제일 중요한 문제였다. 처음엔 트리의 지름을 구하듯이 임의의 점을 기준으로 임의의 위치에서 가장 먼 위치를 기준으로 가장 멀리 있는 지역의 위치를 구했지만, 틀렸다. 그래프에서는 트리의 지름을 구하듯이 거리를 구할 수 없었다. 반례는 아래와 같다.

7 7
LLLLLLL
LLLLLLW
LLLLLWW
LLLLLWW
LLLWWWW
LLWWWWW
LWWWWWW
Output: 7
Answer: 12

결국 어느 지점을 기준으로 정하느냐가 이 문제의 포인트였다. 이 문제에서의 포인트는 양옆에 땅이 있다면 해당 지역은 최소가 될 수 없다는 것이다.

import sys
from collections import deque

def Solution():
    dy = (-1, 0, 1, 0)
    dx = (0, 1, 0, -1)
    res = 0
    inp = sys.stdin.readline
    n, m = map(int, inp().split())
    land = [[s == "L" for s in inp().rstrip()] for _ in range(n)]
    for y in range(n):
        for x in range(m):
            if land[y][x]:
                if 0<=y-1<n and 0<=y+1<n and\
                      land[y-1][x] and land[y+1][x]: continue
                if 0<=x-1<m and 0<=x+1<m and\
                      land[y][x-1] and land[y][x-1]: continue
                q = deque()
                q.append((y, x, 0))
                toVisit = [[True for _ in range(m)] for _ in range(n)]
                toVisit[y][x] = False
                while q:
                    ty, tx, cnt = q.popleft()
                    for d in range(4):
                        tmpY = ty + dy[d]
                        tmpX = tx + dx[d]
                        if n > tmpY >= 0 and m > tmpX >= 0 and \
                        toVisit[tmpY][tmpX] and land[tmpY][tmpX]:
                            toVisit[tmpY][tmpX] = False
                            q.append((tmpY, tmpX, cnt + 1))
                res = max(res, cnt)
    return(res)

if __name__ == "__main__":  
    print(Solution())