[BOJ] 숨바꼭질 3

문제

🥇[골드 5] 12851- 숨바꼭질 3

풀이

수빈이의 현재 위치를 current , 수빈이의 시작 위치를 n, 동생의 위치를 m 으로 정하자.

 

숨바꼭질 2와 같게 똑같이 케이스를 n>m , m==n 일 경우는 BFS를 이용해서 굳이 계산하지 않는다.

남은 경우는 수빈이의 위치가 동생의 위치보다 작을 경우에 대해서 만 BFS를 이용해서 구하면 된다.

 

Python에서 지원하는 Dequeue를 사용해서 문제를 해결 했다. 현재 위치를 currnet라고 하면 current * 2 의 위치로 이동할 경우는 Dequeue의 맨 앞쪽에 넣고, current+1, current-1의 경우는 Dequeue의 맨 뒤쪽에 넣었다.

 

 

그리고 Visited 배열을 선언해서, 몇 초 만에 도착했는지 기록했다.

Visited[current * 2] = Visited[current]

• 0초만에 도착했기 때문에, 전 지역과 같은 시간을 기록
  
  

Visited[current + 1] , Visited[current - 1] = Visited[current] + 1

• 현재 위치에서 부터 도착하는데 1초 가 걸리기 때문에, 전 지역까지 도착하는 시간 + 1을 기록

이를 이용하면, 현재 위치가 m일 때, Vistied[m]을 출력하면 몇 초 만에 도착했는지 알 수 있다.

 

[추가 조건]

그 외에 current는 2m - n + 1보다 무조건 작아야 한다. 이보다 커도 상관은 없지만, 만약 current가 위의 수치를 뛰어넘을 경우, 수빈이가 m에서 n 까지 한 칸씩 걸어서 이동하는 횟수보다 무조건 많아지기 때문에 의미없는 연산이 늘어난다. 연산량을 줄이기 위해서는 위의 조건을 추가해 주는 편이 효율적이다.

코드

#숨바꼭질 3 [GOLD 5]

import sys
from collections import deque

n,m = map(int, sys.stdin.readline().split())

queue = deque()
is_find = False
visited = [-1]*100002

queue.append(n)
visited[n] = 0

if(n==m):
    print(0)
    sys.exit(0)

if(n>m):
    print(n-m)
    sys.exit(0)

while(queue):

    current = queue.popleft()
    if(current == m):
        print(visited[current])
        break

    if (current*2 >= 0 and current*2 < 100001 and current*2 < 2*m-n+1):
        if(visited[current*2] == -1):
            visited[current*2] = visited[current]
            queue.appendleft(current*2)

    dx = [-1,1]
    for i in dx:
        k = current + i
        if(k>=0 and k<100001):
            if(visited[k] == -1):
                visited[k] = visited[current]+1
                queue.append(k)

알고리즘 분류

• 그래프 이론
• 자료구조
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색