[BOJ] 13549 숨바꼭질 3

date

Jul 19, 2023

slug

boj-13549

author

status

Public

문제 링크

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

문제풀이

BFS로 풀었다.

처음에 백트래킹으로 풀려고 했는데, -1, +1부분이 너무 많이 잡아먹어서 포기했다.

문제의 핵심은 Q에넣을때 +, -, *의 순서와 append할때 앞에 넣느냐 뒤에 넣느냐인데

2가지 방법이 있는 것 같았다

*, -, + 순서로 하거나

*을 넣을떄 appendleft, + - 순서로 하거나

둘중 하나라도 잘 안되면 틀렸습니다가 나와서 질문게시판에서 찾아냈다.

파이썬 문제풀이 코드


import sys
from collections import deque
sys.setrecursionlimit(10**5)

N, K = tuple(map(int, input().split()))

q = deque()
q.append((N, 0))

visited = [0] * 300002
level = 1


def bfs():
    if N < K:
            
        while q:
            state, count = q.popleft()
            print(state)
            if state < 0 or visited[state]:
                continue
            visited[state] = 1
            if state == K:
                return count
            
            
            if state < K:
                if not visited[2*state]:
                    q.appendleft((2*state, count))
            if not visited[state+1]:
                q.append((state+1, count+1))
            if not visited[state-1]:
                q.append((state-1, count+1))
    else:
        return (N-K)
        
    
print(bfs())

시간복잡도

O(n*3logn) ?

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력


5 17

예제 출력

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색

데이크스트라

0-1 너비 우선 탐색

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.