[Python] 백준 #1697- 숨바꼭질

문제

---

 

1697번: 숨바꼭질

코드

---

My answer

import sys
from collections import deque

def bfs(idx):
    Q=deque()
    Q.append(idx)

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

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)]

print(bfs(n))

Another answer

from collections import deque

def bfs():
    q = deque()            
    q.append(n)         
    while  q:
        x = q.popleft() 
        if x == k:
            print(dist[x])
            break
        for nx in (x - 1, x + 1, x * 2):    
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x] + 1
                q.append(nx)    

MAX = 10 ** 5           
dist = [0] * (MAX + 1)    
n, k = map(int, input().split())

bfs()

풀이

---

우선 bfs로 문제를 해결하였다. dfs는 끝이없기 때문에 중간에 멈췄어야 했다.

우선 풀이방식은 수빈이가 갈 수 있는 방법 3가지를 direct에 넣는다. 단 2배 멀리가는 것은 수빈이의 현재위치에 따라 달라지므로 [-1,1,0]으로 넣어두고 bfs를 돌면서 0을 현재위치로 바꿔주는 방식을 이용하였다. 

이후 각 방법 한칸뒤로, 한칸 앞으로, 두배로를 반복하면서 동생이 있는 칸에 가는 순간 멈추게 된다.

중간중간 visit에다가 현재 칸을 오기위해 몇 초가 지났는지를 이전칸+1을 해줌으로써 업데이트하면서 진행한다. 

처음에 문제 예시를 통과했음에도 계속 틀렸었는데, 그 이유는 내가 단순하게 수빈이가 동생보다 덜 가있는 경우 즉 n<k인 경우만 생각했기 때문이다. 또한 범위를 유의했어야하는데 visit의 범위를 n,k중 더 큰수 *2배로 잡아줬다. 

아래 링크에 다양한 반례가 있으니, 문제를 푼 것 같음에도 틀릴경우 다양한 반례를 시도해보길 바란다. 

[c++] 백준 숨바꼭질(1679), BFS, 반례모음