백준 2589번 파이썬 문제풀이(보물섬)

---

해당 문제 처음에 문제이해하기가 힘들어서 조금 해맸다. 문제에서 결국 구하라는 것은 육지에서 가장 멀리갈 수 있는 길의 거리를 찾으라는 문제이다. 그냥 육지 지점을 모두 좌표로 저장해서 모든 육지지점에서 부터 출발해서 거리를 계산해서 가장큰 값을 찾는방식으로 했는데 파이썬으로 풀면 시간초과가 난다. 그래서 찾아보니 가운데에 껴있는 육지들 즉, 위아래로 그리고 양옆으로 모두 육지인 애들은 어차피 최대의 거리가 나올수 없기 때문에 그냥 검사하지 않고 넘어가는 식으로 코드를 구성했다. 굳이 따로 구현은 하지 않았지만 관심있으면 찾아보기 바란다.

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
bomool = []
land = []
for i in range(N):
    temp = list(map(str, input()))
    for j in range(len(temp)):
        if temp[j] == 'L':
            land.append((i, j))
    bomool.append(temp)

dr = [-1, 0, 1, 0]  # 행 상 우 하 좌
dc = [0, 1, 0, -1]  # 열 상 우 하 좌


def bfs(r, c):
    queue = deque([[r, c, 0]])
    visited[r][c] = True
    while queue:
        r, c, distance = queue.popleft()

        for i in range(4):

            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M or visited[nr][nc] or bomool[nr][nc] == 'W':
                continue

            visited[nr][nc] = True
            queue.append([nr, nc, distance + 1])

    return distance


max_ = 0
for i in range(len(land)):
    visited = [[False] * M for _ in range(N)]
    distance = bfs(land[i][0], land[i][1])
    if max_ < distance:
        max_ = distance

print(max_)