12851:숨바꼭질2 [백준 문제풀이][Python][CLASS 4]

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

난이도: 골드 4

숨바꼭질(실버 1)의 확장판. 숨바꼭질 같은 경우는 visited를 0과 1로 체크해 주면서 이동하면 bfs로 해결할 수 있었지만, 최단 경로의 개수를 구해야 하므로 단순히 0과 1로만 체크를 하면 안 된다는 걸 알 수 있다. 

아이디어 1

처음에는 단순 bfs를 변형해서 풀 생각을 했다. 최솟값을 찾으면 그걸 저장해 주고 개수를 세주다가 더 작은 최솟값이 나오면 갱신해서 다시 세주는 방식으로 끝까지 세어줬다.

 

시도 1

from collections import deque
n,k = map(int,input().split())
c=[0]*100001
d=deque()
d.append(n)
c[n]=1
s=0
check=True
min_s=1000005
cnt=0
while s<=min_s:
    for _ in range(len(d)):
        p=d.popleft()
        if(p-k > min_s):continue
        if(p==k and s<=min_s):
            if(s<min_s):
                min_s=s
                cnt=1
            else:
                cnt+=1
                continue
        for i in [p+1,p-1,2*p]:
            if 0<=i<=100000:
                d.append(i)
                c[i]=c[p]+1
                
    s+=1
print(min_s)
print(cnt)

결과&실패한 이유

결과는 메모리 초과. 우선 가정에서 잘못 생각한 게 몇 가지가 있었는데, bfs는 너비 우선 탐색이기 때문에 탐색을 할수록 늘어나기만 한다. 따라서 한번 최솟값을 찾으면 그 뒤에 최솟값이 나올 일이 없다. 결국 그 뒤를 계속해서 탐색해 줄 이유가 없다는 뜻이다.

아이디어 2

단순 visited를 가지곤 몇 번 방문했는지 알 수 없다. 따라서 visited에다가 몇 개의 값이 동시에 도착할 수 있는지를 저장해줘야 한다. 또한 원래는 pop을 함과 동시에 체크를 해줌으로써 중복값이 들어가는 걸 방지해 줬으면, 이번엔 몇 개가 도착하는지를 알기 위해서 bfs가 한번 끝날 때마다 체크를 해주고 중복값을 없애지 않는다.

입력:
1 10

시도 1

from collections import deque
n,k = map(int,input().split())
c=[0]*100001
d=deque()
d.append(n)
c[n]=1
s=0
check=True
while len(d)!=0:
    if(c[k]!=0):
        print(s)
        print(c[k])
        check=False
        break
    for _ in range(len(d)):#전체 bfs
        i=d.popleft()
        for j in [i-1,i*2,i+1]:#d에 추가
            if(c[j]==0 and 0<=j<=100000):d.append(j)
    for i in d:c[i]+=1
    s+=1

결과&실패한 이유

결과는 IndexError. 이유를 곰곰이 생각해 보니까 도착지가 10^5에 가까우면 i*2의 값이 c의 범위를 벗어나기 때문에 Index Out of Range 에러가 떴다. 다음은 수정한 코드다.

정답 코드

from collections import deque
n,k = map(int,input().split())
c=[0]*100001
d=deque()
d.append(n)
c[n]=1
s=0
check=True
while len(d)!=0:
    if(c[k]!=0):
        print(s)
        print(c[k])
        check=False
        break
    for _ in range(len(d)):#전체 bfs
        i=d.popleft()
        for j in [i-1,i*2,i+1]:#d에 추가
            if(0<=j<=100000):#범위 조건을 분리
                if(c[j]==0):d.append(j)
    for i in d:c[i]+=1
    s+=1