[백준] 13549 - 숨바꼭질 3 (Python)

문제 링크

알고리즘

• 그래프 탐색
• BFS

Tip

• BFS, 큐를 활용한 풀이
• 파이썬의 내장 자료구조인 deque를 활용해서 순간이동 시
• 관리할 리스트의 크기를 시작과 목표지점의 차이의 2배로 설정 (곱하기 2 연산 때문)

풀이

관리할 리스트 (dp)를 생성 ( dp[n] 은 시작 지점에서 n까지의 최단 거리를 뜻함 )

방문하지 않은 곳은 -1로 설정

시작 지점 dp[start] 을 0으로 설정

목표 지점 dp[finish] 초기값을 abs(start - finish) -> start와 finish의 차이로 설정

큐에서 하나씩 빼고 탐색을 실시한다. 큐에서 뺀 숫자 n의 다음 스텝이 finish보다 클 경우 아래로 한칸 내려오는 알고리즘을 수행하고 n의 다음 스텝이 finich보다 작을 경우 한칸 올라가는 알고리즘 ,두칸을 한번에 올라가는 알고리즘, 총 두가지를 구한다.

코드

# 그림
# 그림

from collections import deque

start, finish = map(int, input().split())

# -1 -> 방문을 한 번도 안함
# n >= 0 -> finish까지 걸리는 시간
dp = [-1] * (max(start, finish) * 2)
dp[start] = 0
dp[finish] = abs(start - finish)
queue = deque([start])
while queue:
    n = queue.popleft()
    if dp[n] >= dp[finish]:
        continue
    if n < finish:
        if dp[n * 2] == -1 or dp[n] < dp[n * 2]:
            dp[n * 2] = dp[n]
            queue.appendleft(n * 2)
        if dp[n + 1] == -1 or dp[n] + 1 < dp[n + 1]:
            dp[n + 1] = dp[n] + 1
            queue.append(n + 1)
        if n != 0 and (dp[n - 1] == -1 or dp[n] + 1 < dp[n - 1]):
            dp[n - 1] = dp[n] + 1
            queue.append(n - 1)
    elif n > finish:
        if dp[n - 1] == -1 or dp[n] + 1 < dp[n - 1]:
            dp[n - 1] = dp[n] + 1
            queue.append(n - 1)

print(dp[finish])



res = []
for n in range(N):
    for m in range(M):
        if not visited[n][m] and picture[n][m] == 1:
            res.append(dfs(1, n, m))
if len(res) == 0:
    print(0)
    print(0)
else:
    print(len(res))
    print(max(res))