[백준 1697번] 숨바꼭질 - 파이썬

문제 링크:

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

1697번: 숨바꼭질

 

---

풀이 유형:

그래프 이론, 그래프 탐색, 너비 우선 탐색

풀이 과정:

이 문제는 1차원상의 좌표에서 수빈이가 동생을 만나기 위한 최소 시간을 도출하는 것이다.
먼저 모든 좌표(100000개)를 0으로 초기화한 리스트를 만든다.
여기에 BFS를 실행하여 특정 위치를 방문하면, 방문한 시간을 표시해준다.
deque을 이용해 큐를 사용하여 풀어보자.

풀이 코드:

# 1697번 숨바꼭질

from collections import deque

# 입력값 받기
n, k = map(int, input().split())
# 움직일 수 있는 최대 좌표는 100000
max_num = 100000
# 해당 위치에 도착했을 때 시간을 표시하는 리스트
visited = [0] * (max_num + 1) # 현재는 시작하지 않았기에 0으로 모두 초기화

# bfs 함수 정의
def bfs():
    q = deque()
    # 수빈이 출발점 위치 큐에 삽입
    q.append(n)
    while q:
        x = q.popleft()
        # 수빈이 위치가 동생의 위치와 같다면 반복문 종료
        if x == k:
            print(visited[x])
            break
        # 이동할 수 있는 방향에 대하여
        for j in (x-1, x+1, x*2):
            # 주어진 범위 내에 있고 아직 방문하지 않았다면
            if 0 <= j <= max_num and not visited[j]:
                # 이동한 위치에 현재 이동한 시간 표시
                visited[j] = visited[x] + 1
                # 큐에 추가
                q.append(j)
# bfs 실행
bfs()

1697번 숨바꼭질