백준 1697. 숨바꼭질
수빈이와 수빈이의 동생이 숨바꼭질을 하고 있다. 수빈이가 걷거나 순간이동을 하여 동생을 찾아낼 수 있다.
가장 최소한의 움직임으로 동생을 찾을 수 있는 경우가 몇 초 후인지 알아낼 수 있도록 코드를 구현해보자.
문제 조건
수빈이는 걷거나 순간이동을 할 수 있다.
- 수빈이의 현재 위치를 X라고 했을 때, 걷는다면 1초 후 (X - 1) 혹은 (X + 1)에 위치한다.
- 수빈이의 현재 위치를 X라고 했을 때, 순간이동을 한다면 1초 후 2*X에 위치한다.
문제 풀이
숫자가 써 붙여진 10만개의 방을 오가면서 수빈이와 수빈이의 동생이 숨바꼭질을 하고 있다고 생각하고 문제를 푼다.
수빈이가 현재 있는 위치 X에서 이동할 수 있는 방은 (X - 1), ( X+ 1), (2*X)이다. 이동한 방에서 또다시 이동가능한 방도 똑같이 (X - 1), ( X+ 1), (2*X), 3가지이다.
여러가지 경우의 수를 모두 탐색하다보면 들어갔던 방을 또 들어갈 수도 있는데, 그때마다 동생이 있는 방에 도달할때까지 초를 다시 세려면 무의미할 것이다.
그래서 어떤 숫자가 적힌 방을 수빈이가 방문했을 때, 수빈이는 몇 초만에 이곳에 왔는지 기록해둔다.
수빈이가 이전에 방문했던 방을 다시 방문하게 되었을 때, 지금 이 방을 방문할 때 걸렸던 시간보다 방문에 써둔 시간이 더 적은 시간일 경우에는 (어차피 최소 시간이 되기는 글렀으므로) 더 이상 탐색을 하지 않는다. (가지치기)
반면에 방문에 써둔 시간보다 더 적은 시간이 걸려서 해당 방에 도착했을 경우에는 최소 시간이 될 가능성이 있으므로 탐색을 계속해 나간다.
모든 탐색이 종료되고 나면, 동생이 있는 방에는 동생을 찾기 위해 올 수 있는 최소 시간이 적혀 있을 것이다.
숨바꼭질 문제에서는 백트래킹 전략을 활용하여 가지치기를 통해 시간 복잡도를 줄이고 해를 구할 수 있다.
DFS, BFS가 가능한 모든 경우를 탐색 하는 방법이라고 했을 때, 백트래킹은 현재 상태를 보관하고 나중에 이를 다시 활용하는 방식이다.
백트래킹 전략으로 파이썬을 푼 코드는 다음과 같다.
파이썬 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | import sys from collections import deque input = sys.stdin.readline def solve(): while q: cur = q.popleft() if cur == k: return visit[cur] nextPos(cur - 1, cur) nextPos(cur + 1, cur) nextPos(cur * 2, cur) def nextPos(nex, cur): # nex 지점이 범위 내에 있고 # 한번도 방문하지 않았거나, 최소 time으로 해당 방을 방문한 경우 if maxSize > nex >= 0 and (0 == visit[nex] or visit[cur] + 1 < visit[nex]): visit[nex] = visit[cur] + 1 q.append(nex) if __name__ == "__main__": n, k = map(int, input().split()) maxSize = 100001 visit = [0] * maxSize q = deque([n]) print(solve()) | cs |
#1697 숨바꼭질 #백준 1697 숨바꼭질 #백준 1697 python ##1697 숨바꼭질 파이썬
'온라인 코딩 테스트 문제 풀이 > 백준 문제 풀이' 카테고리의 다른 글
Python으로 푸는 백준 2178. 미로탐색 (0) | 2019.03.08 |
---|---|
Python으로 푸는 백준 7576. 토마토 (0) | 2019.03.07 |
Python으로 푸는 백준 14502. 연구소 (0) | 2019.02.20 |
python으로 푸는 백준 15671. 오델로 (0) | 2019.02.15 |