BOJ-백준 1697번 숨바꼭질

BOJ-백준 1697번 숨바꼭질

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

✅ Python 정답 코드 입니다. 더보기 클릭!

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int,input().split())

q = deque()
s=0
q.append([n,s])
visited = [False]*100001
if n > k:
    q.append([k,n-k])
else:
  while n!=k:
    n = q.popleft()
    nn=n[0]
    ss=n[1]
    if nn+1==k or nn-1==k or nn*2==k:
      q.append([nn,ss+1]) #동생을 찾음
      break
    offset = [nn-1, nn, nn+1, nn*2]
    offset =list(filter(lambda x: 0<=x and x<=100000, offset))
    for X in offset:
      if not visited[X]:
        q.append([X,ss+1])
        visited[X]=True
print(q[len(q)-1][1])

📌 해설

BFS를 수행하고 큐에 현재 위치를 append합니다. 이미 방문한 위치에는 다시 방문하지 않음으로써 불필요한 이동을 피합니다. 이동 가능한 경우의 수 -1, +1, *2를 동생의 위치와 같아 질 때 까지 반복합니다. 동생의 위치와 같아지면 반복문을 종료하고 마지막 수빈이의 위치와, 지난 시간(초)를 반환합니다. 

 

🚩 주의

수빈이의 위치, 동생의 위치가0~100000까지입력 될 수 있기 때문에 해당 좌표를 필터링 해줄 필요가 있습니다.

수빈이는 전진은 +1, *2를 할 수 있지만 후진은 -1만 가능합니다.

따라서 수빈이의 위치가 100, 동생의 위치가 1일때, 후진으로 -1씩 옮기는 방법말고는 존재하지 않습니다. 따로 if 문을 만들어 주고 처리하는 방법을 선택해 봤습니다. 

 

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int,input().split())

q = deque()
s=0
q.append([n,s])
visited = [False]*100001

1. 필요한 정보를 입력받고 변수를 초기화합니다.

1-1. bfs 탐색을 위한 큐를 선언합니다.

1-2. 큐에 수빈이의 현재 시작 위치, 시작시간을 큐에 append합니다. 

1-3. visited를 최대 입력 위치(100000)만큼 bool 타입 리스트로 초기화합니다.

 

if n > k:
    q.append([k,n-k])

2. 동생의 위치보다 수빈이의 위치가 더 클 경우 수빈이는 -1씩 후진 하는 방법 말고는 동생의 위치와 같아질 방법이 없기 때문에 큐에 동생의 위치, 두 사람의 위치 차이를 append 합니다.  뒤에 나올 while문이 실행 되지 않고 답이 출력됩니다. 

 

else:
  while n!=k:
    n = q.popleft()
    nn=n[0]
    ss=n[1]
    if nn+1==k or nn-1==k or nn*2==k:
      q.append([nn,ss+1]) #동생을 찾음
      break
    offset = [nn-1, nn, nn+1, nn*2]
    offset =list(filter(lambda x: 0<=x and x<=100000, offset))
    for X in offset:
      if not visited[X]:
        q.append([X,ss+1])
        visited[X]=True
print(q[len(q)-1][1])

3. 수빈이의 위치와 동생의 위치가 같지 않을 동안 (같을때 까지)반복하는 while문을 작성합니다. 

3-1. 큐에서 원소 하나를 popleft()해서 n에 저장합니다.

3-2. n의 첫번째 원소를 nn(수빈이 현재 위치)에 저장하고 두번째 원소를 ss(지난 시간)에 저장합니다. 

3-3. 만약 다음 이동에서 동생의 위치와 같아지면, 마지막 위치와 시간을 갱신하고 while문을 종료합니다.

3-4. 아직 동생의 위치와 같아지지 않을 예정이라면, 이동시킬 offset을 초기화 합니다.

    (1). -1, +1, *2, 현재위치 를 원소로 갖는 offset을 생성하고, offset이 0보다 같거나 크고, 100000보다 같거나 작은 offset만 필터링 합니다.

3-5. offset의 좌표가 방문하지 않은 좌표라면 해당 좌표와 시간을 q에 append하고 방문표시를 합니다.

3-6. 동생의 위치와 같아 질때 까지 위 과정을 반복합니다. 

3-7. 마지막 큐에 들어있는 원소의 두번째 원소(지난시간)을 출력합니다.

 

::