[BFS] Python - 2589번, 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

import sys
input = sys.stdin.readline


def bfs(x, y):
    global maxSpentTime
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    spentTimeMap = [[-1]*M for _ in range(N)]
    spentTimeMap[x][y] = 0

    todo = [(x, y)]
    while todo:
        x, y = todo.pop(0)
        for i in range(4):
            curX = x+dx[i]
            curY = y+dy[i]
            if (0 <= curX <= N-1 and 0 <= curY <= M-1):
                if Map[curX][curY] == 'L' and spentTimeMap[curX][curY] == -1:
                    spentTimeMap[curX][curY] = spentTimeMap[x][y]+1
                    maxSpentTime = max(maxSpentTime, spentTimeMap[curX][curY])
                    todo.append((curX, curY))


N, M = map(int, input().split())
Map = []
for _ in range(N):
    curLine = input().rstrip()

    curMapLine = []
    for c in curLine:
        curMapLine.append(c)
    Map.append(curMapLine)

maxSpentTime = -1
for i in range(N):
    for j in range(M):
        if Map[i][j] == 'L':
            bfs(i, j)

print(maxSpentTime)

bfs로 하면 쉽게 해결될 것을, 재귀를 좋아하는 탓에 dfs로 풀려고 했다가 낭패를 보았다.

 

거두절미하고, bfs의 내용을 설명하겠다. 각 위치에 도달한 시간을 저장하는 리스트(spentTimeMap)를 두는데, 아직 방문하지 않았다는 것을 알리는 -1이라는 값으로 초기화를 해둔다. 전형적인 bfs 구조가 진행되고, 방문 조건은 해당 위치가 땅(Map == 'L')이면서, 아직 방문하지 않았을 때(spentTimeMap == -1)이다.

조건 충족 시, 방문할 위치에 도달한 시간을 기록하고, maxSpentTime을 갱신시키며, todo 리스트에 방문할 위치를 추가한다.

 

이런 내용의 bfs를 모든 땅에 대해서 진행시켜주면 된다.