[백준] 2589번 보물섬 - python 파이썬

문제

 

 

 

이 문제를 보면 일단 최단거리라는 단어가 나오기 때문에 BFS일 확률이 높다. 

 

다만 이 문제는 육지에 해당되는 모든 지점에서 다른 지점까지의 최단거리의 값중 최댓값을 구해주는 것이므로 육지를 만날때마다 BFS함수를 실행해주는 형태로 해주면 된다.

 

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

# 첫 번째 줄에서 n과 m을 읽음 (행의 수와 열의 수)
n, m = map(int, input().split())

# n개의 행을 지도 배열로 읽어들임
arr = [list(input().strip()) for _ in range(n)]


def bfs(a,b):
    ans = [[0]*m for _ in range(n)]
    q = deque()
    q.append((a,b))
    #첫번째 지점 방문처리하기 위해 1로 시작
    ans[a][b] = 1
    #각 지점별 최댓값을 저장해줄 변수
    mx = 0

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while(q):
        a,b = q.popleft()
        for i in range(4):
            x = dx[i] + a
            y = dy[i] + b
            #범위안에 있고 육지이고 아직 방문한적없는 칸이면
            if 0<=x<n and 0<=y<m and arr[x][y] != 'W' and ans[x][y] == 0:
                ans[x][y] = ans[a][b] + 1
                mx = max(mx, ans[x][y])
                q.append((x,y))

    #1로 시작했으므로 -1을 해줌
    return mx-1

ans = 0
for i in range(n):
    for j in range(m):
        #육지라면
        if arr[i][j] == "L":
            ans = max(ans,bfs(i,j))
print(ans)

 

 

 

다만 python으로 답안 제출하면 시간초과가 뜬다....

아무래도 모든지점에서 BFS를 실행하다 보니 범위가 작아도 시간초과가 뜨는 것이다. 그래서 pypy3 로 제출해서 정답인정 받았다.