[python]1697번 숨바꼭질

1차원 배열의 bfs로, 정점과 단계 그래프로 생각하는것이 매우 신선한 문제였다.

이것을 그래프 문제 카테고리안에서 못 봤다면 bfs를 떠올리기 힘들었을것 같다.

왜냐하면 문제설명이 동적계획법문제들 같았다.

 

import sys
from collections import deque
input = sys.stdin.readline
subin,bro = map(int,input().split())
visit = [0 for i in range(100001)]
que = deque()
cnt = 0
que.append((subin,cnt))
visit[subin]=1
if subin==bro:    #애초에 둘이 같은 위치에 있을 때, 바로 종료
    print(0)
while que:
    cur = que.popleft()
    if cur[0]*2<=100001 and not visit[cur[0]*2]:
        if cur[0]*2==bro:      #다음 위치가 순간이동일 때
            print(cur[1]+1)
            exit(0)
        visit[cur[0]*2] = 1
        que.append((cur[0]*2,cur[1]+1))
    if cur[0]-1>=0 and not visit[cur[0]-1]:
        if cur[0]-1==bro:		#다음 위치가 한걸을 나아갈 때
            print(cur[1]+1)
            exit(0)   
        visit[cur[0]-1] = 1
        que.append((cur[0]-1,cur[1]+1))
    if cur[0]+1<=bro and not visit[cur[0]+1]:
        if cur[0]+1==bro:		#다음 위치가 한걸을 뒤로 갈 때
            print(cur[1]+1)
            exit(0)
        visit[cur[0]+1] = 1
        que.append((cur[0]+1,cur[1]+1))

중간에 수정한 부분은 if subin==bro부분이다.

입력값으로 수빈과 동생이 같은 위치로 올 수 있지만, while문에서는 그 같은 위치를 잡아낼 부분이 없어 틀린 답이 나왔다.

 

choijaemin16분의 간소화된 풀이

from collections import deque
n,k=map(int, input().split())
MAX=100000
dist=[0]*(MAX+1)   #visit와 cnt의 역할
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):   #x+1,x-1,x*2의 분기를 나누는것을 반복문으로 해결
        if 0<=nx<=MAX and not dist[nx]:
            dist[nx]=dist[x]+1
            q.append(nx)

bomul1128님의 dfs풀이

def find(n, k):   #동생을 이동 시킴
    if n >= k:
        return n - k    #동생이 더 뒤에 있을 때
    elif k == 1:
        return 1        
    elif k % 2:         #동생 거리가 홀수 일 때
        return min (find(n, k + 1), find(n, k - 1)) +1     # +1을 하는 것은 한 단계 진행했다는 뜻     
    else:              #동생 거리가 짝수 일 때
        return min (k - n, find(n, k // 2) + 1)

print(find(*map(int, input().split())))