1697번 숨바꼭질 백준 파이썬

문제: www.acmicpc.net/problem/1697

1697번: 숨바꼭질

sys.exit(<span

import sys
from collections import deque
N,M = map(int,input().split())
loc=[sys.maxsize]*100001
loc[N]=0
 
def bfs(n):
    q=deque()
    cnt=0
    q.append([n,cnt])
    while q:
        a=q.popleft()
        if a[0]==M:
            print(a[1])
            sys.exit(0)
        if a[0]-1>=0:
            if a[1]+1<loc[a[0]-1]:
                loc[a[0]-1]=a[1]+1
                q.append([a[0]-1,a[1]+1])
        if a[0]+1<=100000:
            if a[1]+1<loc[a[0]+1]:
                loc[a[0]+1]=a[1]+1
                q.append([a[0]+1,a[1]+1])
        if a[0]*2<=100000:
            if a[1]+1<loc[a[0]*2]:
                loc[a[0]*2]=a[1]+1
                q.append([a[0]*2,a[1]+1])
 
bfs(N)
 

이 문제를 풀었을 때 약간 완전탐색 느낌이 물씬 느껴져서 기준점으로부터  범위 안에 만족하는 -1,+1,*2를 다 조사하면 되지 않을까 해서 위와 같이 작성하였다. 종료조건은 N이 M이 되는 것이다. 그렇지 못한다면 지금 현재 위치로부터 -1,+1,*2 해서 그 점에 도달한다는 느낌으로 풀면 될 것 같다.

import sys
from collections import deque
def solve(visited,n,k):
    queue=deque()
    queue.append(n)
    while queue:
        x=queue.popleft()
        if x==k:
            print(visited[x])
            return
        for nx in (x+1,x-1,x*2):
            if 0<=nx<100001 and visited[nx]==0:
                visited[nx]=visited[x]+1
                queue.append(nx)
n,k=map(int,input().split())
visited=[0]*100001
solve(visited,n,k)

내 코드가 너무 길이서 어떻게 하면 줄일 수 있을까하고 검색해본결과 풀이과정은 나와 비슷하지만 이분의 코드가 나의 코드보다 깔끔한 느낌이 들어서 올려본다.

나의 경우에는 if문을 통해 해결하였는데 이  분의 경우에는 for _ in (a,b,c): 형태로 문제를 해결하였다. 그리고 방문결과도 큐 안에 넣어서 해결하지 않고 visited로만 해결하였다. 나의 경우에는 큐에 넣은 이유는 혹시나 겹치면 어쩔까 하는 생각에 큐에 넣어서 해결하였는데 생각해보면 2배 증가하는 곳에서 이미 방문할 것이므로 visited==0인 곳에만 방문하면 된다.