2022.02.13 [백준] (python 파이썬) 숨바꼭질2

 

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

---

풀이

다음 문제는 최단거리를 구하는 문제이기 때문에 bfs를 사용하였다.

숨바꼭질 문제와 거의 같은 문제지만 이 문제에선 목표지점까지 최단거리로 갈 수 있는 횟수도 출력해야한다.

그래서 way배열을 만들어 arr[nx]가 0이 아닐 때, arr[nx]=arr[x]+1이면 nx를 최단거리로 갈 수 있는 다른 방법이므로 way[nx]+=way[n]을 해준다.

아래 코드 중, 15번째 줄에 ch=True로 선언해주었다.

이유는 ch로 체크하지않으면 아래의 while문은 10^5승까지 모든 숫자를 계산할 것이다.

ch=end이면 ch를 False로 바꿔준다. 이유는 deq배열에 end값이 제거되어 뽑혔으면 이미 end값이 있는 층은 모두 탐색한것이고 이후 층에서 end값이 나와도 최단거리가 아니기때문에 더 이상 탐색할 필요가 없기 때문이다.

2 7 예시

위의 그림은 2에서 7로 가는 것을 예시로 든것이다. 숫자 옆에 X가 쳐진것은 이미 이전 층에서 방문했거나 범위를 벗어나는 곳이다. 위의 예시에서 4번째 층에서 7에 2번 방문한다. 같은 층에서 방문을 하면 거리는 3으로 같다. 이 다음 층부터는 7에 방문해도 거리는 3보다 크기 때문에 7이 등장한 이후의 층은 탐색할 필요가 없다. 그래서 ch를 이용해 최단거리의 목표지점이 있는 층을 판별하고 이후 층은 탐색하지 않을 수 있다.

 

혼자 생각한 것을 글로 설명하려니 횡설수설한거같다.....하하

from collections import deque
 
n,k=map(int, input().split())
 
#해당 인덱스 값에 최단거리로 몇번 방문했는지 기록
way=[0]*(10**5+1)
#해당 인덱스 값에 도달하기 위한 최단 거리 기록
arr=[0]*(10**5+1)
cnt=0
def bfs(start,end):
    deq=deque()
    deq.append(start)
    arr[start]=1
    way[start]=1
    ch = True
    while deq:
        X=deq.popleft()
        if X==end:
            ch=False
        for nx in (X+1,X-1,X*2):
            if 0<=nx<=10**5:
                if arr[nx]==0:
                    if ch:
                        deq.append(nx)
                    arr[nx]=arr[X]+1
                    way[nx]=way[X]
                elif arr[nx]==arr[X]+1:
                    way[nx]+=way[X]
 
bfs(n,k)
print(arr[k]-1)
print(way[k])