[Python] 백준 #12851- 숨바꼭질 2

문제

---

 

12851번: 숨바꼭질 2

코드

---

My answer

import sys
from collections import deque

def bfs(idx):
    result = 0
    Q=deque()
    Q.append(idx)
    while Q:
        a=Q.popleft()
        direct[2]=a
        if(a==k):
            result+=1
            continue
        for i in range(3):
            new_a=a+direct[i]  
            if(0<=new_a<=limit*2 and (visit[new_a]==0 or visit[new_a]==visit[a]+1)):
                Q.append(new_a)
                visit[new_a]=visit[a]+1
    return result

input = sys.stdin.readline

n,k=map(int,input().split())
direct=[-1,1,0]

limit=max(n,k)
visit=[0 for i in range(2*limit+1)]

result=bfs(n)
print(visit[k])
print(result)

Another answer

풀이

---

숨바꼭질 1번은 엄청 간단하게 풀었는데 조건 하나 추가됐다고 너무 어려워서 결국 다른 분들의 답을 보고 해결했다 ㅠㅠ

우선 숨바꼭질 1은 그냥 최소 도달 경로만 출력하면 됐는데 2번은 최소로 도달하는 경우가 몇번이나 되는지까지도 출력해야했다. 너무 고민이었던게 몇 번 도착했는지를 체크하려면 같은 곳을 여러번 방문하게 될 수도 있는데 예를 들어 1에서 2를 가는 경우 1+1로 갈 수도 있고, 1*2로도 갈 수 있다. 이런 경우 visit을 체크안하자니 그럼 무한으로 루프가 돌게되고, 새로운 리스트를 만들자니, 그럼 2에서 딴데로 갈 때 앞의 경우를 곱해줘야하는건가 이런 별 생각이 다 들었다.

해결책은 그냥 숨바꼭질 1번 코드에 변수1개와 조건 1개만 추가하면 됐는데, 우선 변수는 최종 경로의 개수를 나타내는 result와 조건은 중간중간 큐에 넣기 위해 체크할 때 위의 조건에서 아래 조건으로 하나가 추가된 것이다.

의미는 지금 방문하게 될 곳이 0 즉 처음 방문하는 곳이거나, 지금 방문하는 방법이랑 똑같은 가지수 일 경우 즉 

아까 든 예시 2로 갈때 이 때 a=1이고 new_a는 반복문을 돌며 2,2,0을 돌게된다. 이때 처음 2가 들어가면 visit[2]=1로 바뀌고, 다음 또 2가들어갔는데 이미 저장되어 있는 1과 지금 또 1이 같으므로, 그냥 넘어간다. 사실 이 조건의 경우는 제일 마지막 k에 도달할 때만 생각하면 되는데 어떠한 방법으로든 k에 도달할 때 또 k가 나오면 result를 올려주면 된다. 즉 방금 설명한 조건은 visit가 있어도 큐에 숫자를 넣기위해 추가해준 것이다. 

(너무 주저리 주저리)

요약: 한 곳에 방문하는 여러 경우의 수를 새기위해서는 방문을 중복으로 체크해줘야한다. 우리는 최종 k에 도달하는 경우만 새면되고 그러기위해서는 큐에 아까 들어간 숫자도 들어가기만 하면 된다. 따라서 이미 지났던 칸이라도 조건에 만족하면 큐에 넣어준다. 

if(0<=new_a<=limit*2 and visit[new_a]==0):

if(0<=new_a<=limit*2 and (visit[new_a]==0 or visit[new_a]==visit[a]+1)):

아래 링크에 다양한 반례가 있어여

https://www.acmicpc.net/board/view/56215

글 읽기 - 이거 반례 찾으면 500원 드립니다