2589 보물섬 [BFS]

2589 보물섬

bfs 문제인건 알고 있었으나 python 특유의 느린속도때문에 최대입력이 50x50이여도 각 칸마다 bfs로 brute force방식으로 하기엔

안될거같은 생각이 들었음에도,, 해보니 그냥 된다?!

최악의 수인 50x50 모두 Land 일경우 

2500번을 visit배열을 생성하고 6252500번 pop, append를 반복하기에 

당연히 시간도 테스트당시 10초이상걸리고 시간초과가 뜨겠거니 하고 다른방식을 생각하다

도저히 메모제이션이나 시간을줄일 방법이 안떠올라 안되면 c++로 해보자하고 해봤는데 정답으로 나온다....

 그냥 간단한 문제였던걸로 생각하자.

import collections


def bfs():
    direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    max_cnt = 0
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'L':
                visit = [[0] * n for _ in range(m)]
                q = collections.deque()
                q.append((i, j))

                while q:
                    y, x = q.popleft()
                    for dy, dx in direct:
                        ny = y + dy
                        nx = x + dx
                        if ny < 0 or nx < 0 or ny >= m or nx >= n:
                            continue
                        if board[ny][nx] == 'L' and visit[ny][nx] == 0:
                            visit[ny][nx] = 1 + visit[y][x]
                            q.append((ny, nx))
                max_cnt = max(max_cnt, visit[y][x])
    print(max_cnt)


m, n = map(int, input().split())
board = []

for i in range(m):
    board.append(input())

bfs()