백준 / 1697번 숨바꼭질 - BFS / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1697번 숨바꼭질

문제 사이트: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

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초만에 동생을 찾을 수 있다.

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

• 데이터를 추가한 사람: arat5724, cohan, djm03178
• 문제를 번역한 사람: author6

비슷한 문제

• 12851번. 숨바꼭질 2
• 13549번. 숨바꼭질 3
• 13913번. 숨바꼭질 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 로 최적의 해가 구해졌을때 바로 리턴하는 이유: 가지를 한 층씩 탐색한 후 이어나가는 것(너비우선 탐색)이기 때문에 최적의 해가 나오면 바로 리턴하면 된다.