2589. [Python]보물섬

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 512MB
• 너비 우선 탐색

 

3. 파이썬 코드

 

from collections import deque
import sys

input = sys.stdin.readline
# 방향 탐색
direction = [(0,-1), (-1,0), (0,1), (1,0)]
# 너비 우선 탐색
def BFS(x,y):
    global max_value
    visited = [ [0] * M for _ in range(N) ]
    visited[x][y] = 1
    queue = deque([(x,y)])
    while queue:
        check = queue.popleft()
        for k in range(4):
            ny = check[0] + direction[k][0]
            nx = check[1] + direction[k][1]
            # 범위 내 존재
            if 0 <= ny < N and 0 <= nx < M:
                # 땅이고 방문하지 않았을 경우
                if matrix[ny][nx] == "L" and visited[ny][nx] == 0:
                    # 방문처리 후 최대값 비교
                    visited[ny][nx] = visited[check[0]][check[1]] + 1
                    if visited[ny][nx] > max_value:
                        max_value = visited[ny][nx]
                    queue.append((ny,nx))

N, M = map(int,input().split())

matrix = [ list(map(str,input())) for _ in range(N) ]


max_value = 0

for i in range(N):
    for j in range(M):
        if matrix[i][j] == "L":
            BFS(i,j)

print(max_value-1)

 

4. 문제를 풀고난 후 생각

 

• 단순한 BFS 를 한번 돌려서 해결할 수 있을거라 생각했고 실제로 한번만 돌렸을 때 값이 나오는 것을 보고 쉬운 문제라고 판단했다.
• 모든 경우의 수를 다 고려해서 "L"(육지)에서 BFS를 모두 돌려 거기서 거리가 제일 먼 값이 나와야 문제에서 요구하는 정답이 된다는 것을 알게 되었고, 모든 "L"에서 BFS를 돌렸다.
• Python3 로는 55% 에서 시간초과가 발생하지만 Pypy3 로는 시간초과 없이 통과됐다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 너비 우선 탐색