[BOJ] 숨박꼭질3 13549

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

 

1. 문제 이해 및 해결과정

- 우선순위 를 생각해야한다. - 이 문제는 가중치가 있는 BFS이다.  - 0초로 이동하는 것은 X-1,X+1 (1초) 보다 우선순위를 가진다.  - 순간이동을 하면(2X) , deque의 뒤에 추가한다. - X-1,X+1, deque의 앞에 추가한다. - 이 순서로 추가하면, popleft로 인해 앞에서 부터 pop하여 cur을 찾으므로 우선순위에 따라 이동할 수 있다.

 

2. 풀이방법

 1. BFS

#숨바꼭질3
#https://www.acmicpc.net/problem/13549
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

n,k=map(int,input().split())
MAX=100000
time=[-1]*(MAX+1) #순간이동은 0초이므로 -1로 초기화
Q=deque()
Q.append(n)
time[n]=0
while Q:
    cur=Q.popleft()
    if cur == k:
        print(time[cur])
        break

    next = cur * 2
    if 0 <= next <= MAX and time[next] == -1:
        Q.appendleft(next)
        time[next] = time[cur]
    next = cur-1
    if 0<=next<=MAX and time[next]==-1:
        Q.append(next)
        time[next] = time[cur] + 1
    next = cur+1
    if 0 <= next <= MAX and time[next] == -1:
        Q.append(next)
        time[next] = time[cur] + 1

 2. BFS for문 한번에 변경

#숨바꼭질3
#https://www.acmicpc.net/problem/13549
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

n,k=map(int,input().split())
MAX=100000
time=[-1]*(MAX+1) #순간이동은 0초이므로 -1로 초기화
Q=deque()
Q.append(n)
time[n]=0
while Q:
    cur=Q.popleft()
    if cur == k:
        print(time[cur])
        break

    for next in (cur - 1, cur + 1, cur * 2):
        if 0 <= next <= MAX and time[next] == -1:
            if next==cur*2: #순간이동이라면
                Q.appendleft(next)
                time[next] = time[cur]
            else:
                Q.append(next)
                time[next] = time[cur] + 1

 

3. 오답원인

- 순간이동을 할 경우, 0초이므로 time을 -1로 초기화 하였는데 첫 시작점을 0부터 시작해야한다. 

time[n]=0

 

4. 알게된 점