[백준] 1697번 숨바꼭질 (Python 파이썬)

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제 설명

수빈이는 동생과 숨바꼭질을 한다. 수빈이의 좌표는 N, 동생의 좌표는 K이다.

수빈이의 위치가 X일 때, 1초 후에 X+1, X-1 X*2 중에 하나로 이동할 수 있다.

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지를 구하면 된다.

---

풀이 과정

BFS를 이용하여 풀었다. 변수에 대해 먼저 설명하자면, count는 일 수, flag는 찾은 여부를 나타내는 변수이다.

today_queue는 오늘 안에 도착할 지점, queue는 내일 방문할 지점 이라고 생각하면 된다.

과정은 다음과 같다.

 

1) queue에 시작점을 넣어주고 시작점을 visit처리 한다.

2) queue에 원소가 남아있을 때 까지 bfs를 돌린다. ( 시작 시는 1개 )

3) bfs안에서 today_queue를 만들어 queue에 있는 원소들을 모두 가져온다.

4) 오늘 할당량을 모두 비울 때 까지 숨바꼭질을 진행하며 내일 방문할 곳은 queue에 삽입한다.

5) 오늘 방문할 지점에 동생의 좌표가 존재하면 flag = 1 처리를 하고 탈출한다.

 

from collections import deque
import copy

n, k = map(int, input().split())
visited = [False] * 100001
count = 0
flag = 0

def bfs():
    global count
    today_queue = copy.deepcopy(queue)

    while today_queue:
        x = today_queue.popleft()
        queue.popleft()
        if x == k:
            global flag
            flag = 1
            return
        for i in range(3):
            if i == 0:
                nx = x + 1
            elif i == 2:
                nx = x - 1
            else:
                nx = x * 2
            if nx < 0 or nx > 100000:
                continue
            if not visited[nx]:
                queue.append(nx)
                visited[nx] = True

    count += 1


queue = deque()
queue.append(n)
visited[n] = True

while queue:
    bfs()
    if flag == 1:
        print(count)
        break

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !