[Python] 1697번 숨바꼭질

문제

https://www.acmicpc.net/problem/1697

풀이과정

• BFS 사용 최단 시간을 구하는 것이기에 BFS를 사용한다.
  

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

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

nm_max = 100000
visited = [0]*(nm_max+1)

def BFS():
    q = deque()
    # 출발위치
    q.append(n)

    while q:
        x = q.popleft()
        # 같은 위치가 되면 종료
        if x == k:
            print(visited[x])
            break
        for i in (x-1, x+1, x*2):
            if 0 <= i <= nm_max and visited[i] == 0:
                visited[i] = visited[x]+1
                q.append(i)

BFS()

nm_max = 100000
visited = [0]*(nm_max+1)

최대 위치와 방문 여부를 저장하는 리스트를 만들어준다.

• BFS 함수 큐를 만들어주고 시작위치를 넣은 다음, 큐가 비어있지 않은 동안 과정을 반복한다.

    while q:
            x = q.popleft() # 확인할 원소를 가져온다.
            # 같은 위치가 되면 종료
            if x == k:
                print(visited[x])
                break
            for i in (x-1, x+1, x*2): # 각 위치를 
                if 0 <= i <= nm_max and visited[i] == 0: # 최대범위를 넘지 않고 방문하지 않았을 때
                    visited[i] = visited[x]+1 # 방문 처리 
                    q.append(i)

메모리: 35108KB
시간: 100ms

for in문이 여러가지를 넣을 수도 있었다..