[BOJ][Python] 백준 2589번 : 보물섬

- 문제 링크

https://www.acmicpc.net/problem/2589

- 풀이

bfs로 풀었다. 문제를 보면 알겠지만 범위 내에서 모든 육지를 다 체크해야 하는 완전 탐색 문제이다. 코드를 보면 알겠지만 그냥 bfs에서 사알짝 응용 버전이다. 별로 어렵지 않았다. 근데 정답률이 37% 밖에 되지 않아서 조금 이상하긴 했다. 

-  코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x, y):
    visited = [[0] * M for _ in range(N)]
    queue = deque()
    queue.append((x, y, 0))
    visited[x][y] = 1
    distance = 0
    while queue:
        a, b, d = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] == 'L' and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    distance = d + 1
                    queue.append((nx, ny, d + 1))

    return distance

N, M = map(int, input().split())
graph = []
res = 0
for i in range(N):
    graph.append(list(map(str, input().rstrip())))

for i in range(N):
    for j in range(M):
        if graph[i][j] == 'L':
            res = max(res, bfs(i, j))

print(res)

 

참고로 python3로 제출하면 시간 초과가 뜨고, pyp3으로 제출해야 시간초과가 뜨지 않는다. 파이썬은 시간초과가 너무.. 잘 뜬다. c++로 공부를 할 걸 그랬다. 코딩 테스트에서도 이런 문제만 나왔으면~~