파이썬) 보물섬-BOJ

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

2589번: 보물섬

 

이 문제는 조금 난해했다.

우선 문제를 읽자마자 풀이 방법을 떠올렸고 그대로 코드로 옮겼다.

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


n, m = map(int, input().split())

arr = []
answer = 0

for i in range(n):
    str = input()
    arr.append(str)


dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]


def bfs(i, j):
    q = deque()

    q.append((i, j))

    visit = [[0]*m for _ in range(n)]
    visit[i][j] = 1
    return_v = 0
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < n and 0 <= ny < m:
                if visit[nx][ny] == 0 and arr[nx][ny] == 'L':
                    visit[nx][ny] = visit[x][y] + 1
                    return_v = max(return_v, visit[nx][ny])
                    q.append((nx, ny))

    return return_v - 1


for i in range(n):
    for j in range(m):
        if arr[i][j] == 'L':
            cnt = bfs(i, j)
            answer = max(cnt, answer)


print(answer)

우선 내가 작성한 코드이다.

겉으로 보면 아무런 이상이 없으나 막상 채점을 시작하면

보다시피 시간초과가 발생한다...

하다하다 결국 다른 이의 코드를 참조했으나 번번히 시간초과가 발생했다.

그러다 통과한 코드를 보았다.

from collections import deque
H,W = map(int,input().split())
field = list()
direction = [[0,1],[1,0],[-1,0],[0,-1]]

for _ in range(H):
    field.append(list(input()))
def bfs(rx,ry):
    visited = [[0]*W for _ in range(H)]
    q = deque([[rx,ry]])    
    visited[ry][rx]=1
    maxcnt = 0
    while q:
        x,y = q.popleft()
        for dx,dy in direction:
            nx,ny = dx+x,dy+y
            if 0<=nx<W and 0<=ny<H and field[ny][nx]=='L' and visited[ny][nx]==0:
                visited[ny][nx]=visited[y][x]+1
                if maxcnt < visited[ny][nx]:maxcnt=visited[ny][nx]
                q.append([nx,ny])
    return maxcnt-1
answer = 0
for i in range(H):
    for j in range(W):
        if field[i][j]=='L':
            tmp = bfs(j,i)
            if tmp>answer:
                answer = tmp
print(answer)

결국 통과했지만 어디서 시간초과가 발생했는지 참 의문이다..