[백준 #2589 파이썬] 보물섬

bfs를 연습해보기 가장 적절한 문제라고 생각한다!

아마 실버에서 골드정도로 올라갈 때 가장 적합한 문제?

기초 예제문제정도로 생각된다!

 

생각

1. 어떤 지점이 시작지점인지 모른다.

2. 어떤 지점이 끝지점인지 모른다.

 

구현

전체 탐색을 해야만한다.

방문 여부 처리를 해야 한다.

값 갱신 처리를 해야 한다.

모든 bfs결과값을 저장하고 그중 최대값을 뽑기만 하면 된다.

from collections import deque
n,m = map(int,input().split())
field = [list(map(str,input()))for _ in range(n)]
ans = []

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

def bfs(a,b):
    q = deque()
    q.append((a,b))
    visited[a][b] = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx,ny = dx[i]+x,dy[i]+y
            if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0 and field[nx][ny] == 'L':
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx,ny))
    return visited[x][y]
    
for i in range(n):
    for j in range(m):
        visited = [[0]*m for _ in range(n)]
        if field[i][j] == 'L':
            k = bfs(i,j)
            ans.append(k)
print(max(ans)-1)