[알고리즘][파이썬]1697-숨바꼭질

 

 

문제

코드

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().strip().split())

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

MAX = 10 ** 5               # 시간초과 방지
visited = [0] * (MAX + 1)      # 이동하는 시간 count

bfs()

문제설명
출발지 N에서  도착지 K까지 (+1,-1,*2)로 이동하는 데 걸리는 시간을 구하는 문제이다.

접근방법
최단 거리를 구하는 유형으로 BFS 알고리즘을 이용할 수 있다.

코드설계
현재 위치 x에 (x-1),(x+1),(x*2)가 계속 연결되어 있는 그래프를 다룬다고 생각한다.
해당 인덱스 visited배열에 탐색 여부 겸 시간을 기록한다.


발생한 오류
1. 런타임 에러 

100000이 넘어가는 숫자가 배열 인덱스로 접근 할 때 발생한다.

2. 메모리 추가 
visited를  제거하고 코드를 짜보고 싶어서 해봤더니 메모리 초과가 발생했다.
하나의 숫자에 여러 가지 경로로 접근이 가능한데 visited를 설정을 안 하면 한 가지 숫자에서 여러 번 계산하게 된다.
따라서 탐색을 한 숫자는 visited로 체크가 반드시 필요하다.

3.시간 초과
nv의 조건문을 <k+2로 두었는데 k의 범위가  (0 ≤ K ≤ 100,000)로 시간 초과가 발생하게 된다.
이를 방지하기 위해 nv <=100000으로 두어야 한다.