[백준/bfs] 2589번 : 보물섬

- 문제 : https://www.acmicpc.net/problem/2589

 

 

정답 풀이 

두 보물 간의 거리 중 최댓값을 구하는 문제다. 근데 두 보물의 위치가 정확히 나온 것은 아니고, "보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다." 문구에서 처럼 두 보물의 위치는 상황마다 달라서 매번 구해야 한다. 이는 모든 육지지점(L)에 대해서 bfs로 탐색 후 가장 긴 길이 중 최댓값을 출력하라는 걸로 이해했다. 

 

1. 주어진 행렬에서 모든 L 지점을 시작으로 bfs를 진행한다.

2. 지나온 칸 개수를 visit에 기록하고, 각 케이스에서 visit의 최댓값을 result에 추가한다.

3. max(result) - 1 값을 출력한다. (두 지점 간의 거리를 출력하기 때문에 1을 뺐다. 1 안 빼면 틀린다!) 

 

# python3 - 시간 초과, pypy3 - 성공 하는 코드
def bfs(i, j, visit):
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = [[i, j]]
    visit[i][j] = 1
    while queue:
        x, y = queue.pop(0)        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == 'L' and not visit[nx][ny]:
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny])
                    
        
n, m = map(int, input().split())
matrix = [list(input()) for _ in range(n)]

result = []
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 'L':
            visit = [[0] * m for _ in range(n)]
            bfs(i, j, visit)
            answer = 0
            for k in range(n):
                answer = max(answer, max(visit[k]))
            result.append(answer)
            
            
print(max(result) - 1)