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

🧩문제 해석

수빈이와 동생은 일직선 상에 위치하고 수빈이는 1초에 x-1, x+1, 2*x 로 이동할 수 있다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하면 된다.

 

📚풀이

BFS를 사용하여 풀었다.
방문을 체크하기 위한 visited 리스트를 생성하였다.
큐에 현재 위치와 현재 누적 초를 같이 저장하여, 이동 할 때마다 초를 누적 시켜주었다.
이동 가능 위치는 arr 리스트로 만들어주었고, arr 요소 중 아직 방문 하지 않았고, 0~100000 사이 값이라면 방문하고 큐에 삽입 하였다.
그렇게 하여 k와 같은 값을 찾으면 현재 누적 초를 출력하였다.

만약 시작부터 동생과 수빈이가 같이 있다면 이동할 필요 없기에 0을 출력한다. 그리고 동생이 수빈이보다 뒤에 위치한다면 뒤로 1칸씩 이동하는 방법 밖에 없고 이동시간은 n-k이기에 BFS 돌리지 않고 바로 n-k를 출력하였다.

위 과정을 놓쳐서 처음에 틀렸습니다 판정을 받았다.

 

💻 코드

from collections import deque

def bfs(): # BFS 정의
    queue = deque()
    queue.append((n, 0)) # 처음 수빈이 위치와 누적 초를 삽입
    visited[n] = True # 처음 수빈이 위치 방문 처리
    while queue: # 큐가 빌때까지
        c, cnt = queue.popleft()
        if c == k: # 만약 이동 위치와 동생위치가 같다면 카운트 출력
            print(cnt)
            break
        else: # 다르다면 이제 이동함
            arr = [c-1, c+1, 2*c] # 앞으로 한칸, 뒤로 한칸, 순간이동
            for i in arr:
                if 0 <= i <= 100000: # 이동범위, 필요없는 값으로 탐색가는 것을 줄이기 위한 구문
                    if not visited[i]: # 방문하지 않았다면
                        visited[i] = True # 방문 처리하고
                        queue.append((i, cnt+1)) # 큐에 삽입, 1초 경과


n, k = map(int, input().split()) # 수빈이 위치와 동생위치입력 받음
visited = [False for i in range(100001)] # 방문체크
if n == k: # 시작부터 수빈이와 동생이 같은 위치에 있다면 움직이지 않음
    print(0)
elif n > k: # 동생이 수빈이보다 뒤에 위치한다면 탐색필요없고 그냥 뒤로 한칸씩 이동하면 된다. 순간이동을 못한다는 뜻
    print(n-k)
else: # BFS 함수 호출
    bfs()

 

🔗 문제 링크 : 숨바꼭질

1697번: 숨바꼭질

 

700