백준 / 1697번 숨바꼭질 - BFS / Python 파이썬
*문제 출처는 백준에 있습니다.
문제 제목: 1697번 숨바꼭질
문제 사이트: https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
| 2 초 | 128 MB | 202415 | 58435 | 36779 | 25.313% |
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1 복사
5 17
예제 출력 1 복사
4
힌트
수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.
나의 첫번째 풀이 (DFS, BFS 비교하려고 둘 다 짬)
import sys
from collections import deque
input = sys.stdin.readline
INF = 1e9 # 무한
def dfs(now,cnt,visited):
global min_cnt
print(now,cnt)
if min_cnt < cnt:
return
if now > k+2:
return
if 0 <= now <= k+1 and visited[now] == False:
visited[now] = True
if now == k:
if cnt < min_cnt:
min_cnt = cnt
else:
direct = [now * 2,now + 1,now - 1]
for i in range(3):
now = direct[i]
dfs(now,cnt+1,visited)
else:
return
def bfs(start,visited):
m_cnt = INF
queue = deque()
queue.append([start,0])
while queue:
now, cnt = queue.popleft()
direct = [now * 2,now + 1,now - 1]
for i in range(3):
now = direct[i]
if 0 <= now <= k+1 and visited[now] == False:
visited[now] = True
if now == k:
if cnt < m_cnt:
m_cnt = cnt
elif now <= k+1 and now != k:
queue.append([now,cnt+1])
return m_cnt
if __name__ == "__main__":
n,k = map(int,input().split())
min_cnt = INF
visited = [False for i in range(k+2)]
if n == k :
print(0)
else:
print(bfs(n,visited)+1)두번째 풀이
BFS 의 탐색이 최소값으로 잘 찾는 것을 확인
문제에서 주어지는 최대 입력값을 코드에 넣어서 구현 ( 일단 전체 범위로 보았을 때 최적의 해를 구해야하기 때문)
k보다 n이 더 클때는 뒤로 가는 것이 최적의 해임
(n // 2 로 순간이동할 수 없기 때문에 n*2 나 n+1 로 이동하면 증가만하지 뒤로 못감)
if k < n :
print(n-k)
else:
print(bfs(n,visited))
최종 나의 풀이
import sys
from collections import deque
input = sys.stdin.readline
INF = 1e9 # 무한
def bfs(start,visited):
m_cnt = INF
queue = deque()
queue.append([start,0])
while queue:
now, cnt = queue.popleft()
if now == k:
return cnt
direct = [now * 2,now + 1,now - 1]
for i in range(3):
now = direct[i]
if 0 <= now <= k+1 and visited[now] == False:
visited[now] = True
queue.append([now,cnt+1])
return m_cnt
if __name__ == "__main__":
n,k = map(int,input().split())
visited = [False for i in range(100001)]
if k < n :
print(n-k)
else:
print(bfs(n,visited))
※ 알아야 할 것
- bfs 로 최적의 해가 구해졌을때 바로 리턴하는 이유: 가지를 한 층씩 탐색한 후 이어나가는 것(너비우선 탐색)이기 때문에 최적의 해가 나오면 바로 리턴하면 된다.