[Baekjoon Online Judge] 백준 1697번 숨바꼭질(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1697번 숨바꼭질

(Python)

(글쓴날 : 2020.03.30)

 

---

* Baekjoon Online Judge, 백준 1697번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1697번 숨바꼭질

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

2) 풀이 과정

0부터 100000사이의 숫자인 N과 M이 주어지고, N이 1초에 -1, +1 또는 *2씩 변화할 수 있을 때 N이 M과 같아지는 가장 빠른 시간이 몇 초인지 출력하는 문제입니다.

 

저의 경우, BFS를 적용해 문제에 접근하였습니다.

깊이마다 큐의 크기를 재서 해당 크기만큼 탐색하는 반복문을 돌리고, 반복문이 종료될 때마다 1초씩 추가하여 최종 시간을 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, queue
input = sys.stdin.readline
 
 
def BFS(q):
    global K, visit, dx, time
 
    while not q.empty():
        size = q.qsize()
 
        for _ in range(size):
            x = q.get()
            
            if x == K:
                print(time)
                exit()
            
            if visit[x] == False:
                visit[x] = True
 
                for way in range(3):
                    if way == 2:
                        ii = x * dx[way]
                    else:
                        ii = x + dx[way]
 
                    if ii < 0 or ii > 100000:
                        continue
                    
                    q.put(ii)
        time += 1
        
 
N, K = map(int, input().split())
visit = [False] * 100001
dx = [-1, 1, 2]
time = 0
 
q = queue.Queue()
q.put(N)
 
BFS(q)

---