[Python] 백준 1697 숨바꼭질

 

문제 분석

• 시작 위치 : N, 도착 위치 : K
• X에서
  • 걷는 다면 : X-1, X+1
  • 순간이동 : X*2

 

풀이

• 각 이동하는 칸에 대하여 최단 거리 구하기
• 각 칸에 대한 이동 시간 기록
• dp
• dfs ?

 

코드 설계

 

 

정답 코드

1차 - 메모리초과

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())

def dfs() :
    d = deque()
    d.append((n, 0))

    while d :
        x, cnt = d.popleft()

        if x == k:
            print(cnt)
            break

        d.append((x + 1, cnt + 1))
        d.append((x - 1, cnt + 1))
        d.append((x * 2, cnt + 1))

dfs()

 

2차 - 런타임에러

갔던 곳에 대해서 또 확인하지 않도록 visited 배열 선언

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())

v = [False for _ in range(100001)]

def dfs() :
    d = deque()
    d.append((n, 0))
    v[n] = True

    while d :
        x, cnt = d.popleft()

        if x == k:
            print(cnt)
            break

        if not v[x+1] :
            d.append((x + 1, cnt + 1))
            v[x+1] = True

        if not v[x-1] :
            d.append((x - 1, cnt + 1))
            v[x - 1] = True

        if not v[x*2] :
            d.append((x * 2, cnt + 1))
            v[x * 2] = True

dfs()

 

3차 - 통과

범위 체크 추가

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())

v = [False for _ in range(100001)]

def dfs() :
    d = deque()
    d.append((n, 0))
    v[n] = True

    while d :
        x, cnt = d.popleft()

        if x == k:
            return cnt

        if (0 <= x+1 <= 100000) and not v[x+1] :
            d.append((x + 1, cnt + 1))
            v[x+1] = True

        if (0 <= x-1 <= 100000) and not v[x-1] :
            d.append((x - 1, cnt + 1))
            v[x - 1] = True

        if (0 <= x*2 <= 100000) and not v[x*2] :
            d.append((x * 2, cnt + 1))
            v[x * 2] = True

print(dfs())