[BOJ] 2539번 보물섬 / 사용언어 : 파이썬(python)

※ 문제링크

2589번: 보물섬

해당 문제는 브루스포트 알고리즘과 BFS를 활용하여 푸는 문제였다. 간단하게 말해서 그냥 BFS로 탐색할 수 있는 함수를 구현하고, 모든 좌표에서 모든 경우의 수를 찾아서 비교한 후 결과값을 출력하면 되는 문제였다. 문제 조건에서 보물은 서로 가장 멀리 떨어져있고, 최단거리로 이동하라고 나와있는데, 해당 조건은 그냥 가장 먼 좌표 2개의 거리를 구하면 된다는 걸 두번 말하고 있는 것이니 가장 거리가 먼 육지좌표 2개의 거리를 출력할 수 있게 하면 된다.
문제를 푸는 개념은 위와 같으나, 해당 문제를 Python3로 통과하기위해서는 자료형 등과 같은 다양한 부분에서 최적화가 까다롭게 들어가야 하는 문제가 있었다. 최적화를 안해도 PyPy3로는 손쉽게 통과가 가능하니 참고하기 바라며, 아래 코드는 PyPy3로만 통과 가능하니 참고하면 좋을 것 같다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들 바탕으로 지도를 2차원 배열로 작성하고, 배열을 작성하면서 육지의 좌표를 따로 저장해준다.

2. 사방위를 탐색할 수 있게 deque를 사용하여 BFS함수를 구현하고, 그 과정에서 최댓값을 갱신할 수 있게 작성한다.

3. 반복문을 활용하여 저장해둔 육지좌표들을 하나씩 BFS함수에 대입하며, 모든 경우의 수를 확인한다.

4. 반복문 종료 후 결과값을 출력한다.
+ 시간 및 메모리 절감을 위해 sys를 사용하였으며, 문자열 입력시에는 개행문자를 제거해줬다.

 

from collections import deque
import sys

# input = sys.stdin.readline
N, M = map(int, input().split()) # N: 세로, M: 가로
field = []
lands = []
for y in range(N):
    inputValue = list(input().rstrip())
    field.append(inputValue)
    for x in range(M):
        if inputValue[x] == 'L':
            lands.append([x, y])

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

def bfs(x, y):
    queue = deque()
    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[y][x] = True
    queue.append([x, y, 0])

    cnt_time = 0
    while queue:
        x, y, time = queue.popleft()
        if cnt_time < time:
            cnt_time = time
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if visited[ny][nx] == False and field[ny][nx] == "L":
                    queue.append([nx, ny, time+1])
                    visited[ny][nx] = True
    global ans
    if ans < cnt_time:
        ans = cnt_time
    return 

for x, y in lands:
    bfs(x, y)
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.