[Python] 백준 알고리즘 13549번 - 숨바꼭질 3

[Python] 백준 알고리즘 13549번 - 숨바꼭질 3

문제 출처 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

13549 - 문제 내용

 

접근방식

 그래프 탐색 방식의 BFS 방식을 이용했다. 문제의 경우 그래프가 주어져있지는 않지만 각 숫자의 번호를 그래프의 노드로 보고 BFS 방식을 적용하였다. 숨바꼭질 3 문제는 기존의 숨바꼭질 문제가 존재하고 문제에 조건을 추가하여 난이도를 올린 문제이다

 이전의 숨박꼭질 문제와 다른 점은 순간이동이라는 부분이 추가된 것이 있다. 순간이동의 경우 소요되는 시간이 0이므로 앞, 뒤로 움직이며 시간이 1초씩 흐르는 부분보다 앞에 배치가 되어야 한다.  

# 순간이동의 경우
    Nstart = start * 2
    if Nstart < len(check) and not check[Nstart]:
        q.append((Nstart, time))

# 앞 뒤로 움직이는 경우
    for i in (start - 1, start + 1):
        if 0 <= i < len(check) and not check[i]:
            q.append((i, time + 1))

 또한 check라는 리스트를 선언하여 지나간 구간은 다시 한 번 큐에 들어가지 않게 코드를 넣어주었다

from collections import deque

# 필요한 check 리스트와 deque 선언
check = [False] * 100001
q = deque()

구현 코드

from collections import deque

n, k = map(int, input().split())

check = [False] * 100001
q = deque()
q.append((n, 0))

while q:
    start, time = q.popleft()

    if not check[start]:
        check[start] = True

    if start == k:
        print(time)
        break

    Nstart = start * 2
    if Nstart < len(check) and not check[Nstart]:
        q.append((Nstart, time))

    for i in (start - 1, start + 1):
        if 0 <= i < len(check) and not check[i]:
            q.append((i, time + 1))

 

 

보충할 점

 

•  DFS ( 재귀 / stack ) 방식