[BOJ] 숨바꼭질 4

문제

🥇[골드 4] 12851- 숨바꼭질4

풀이

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

 

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

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

 

 

자료구조 queue를 이용하면 문제를 간단하게 해결할 수 있다. 일반적인 BFS와 같게, queue를 선언하고, 다음 도착지를 queue에 넣는다. 종료 조건은 동생 위치에 도착했을 때로 정한다.

 

그리고 Visited 배열을 선언해서, Visited 배열에 들어가는 값을, 현재 위치에 도착하기 위해서 출발한 위치로 정한다. 예를 들어서 3에서 출발해서 5에 도착했다면, visited[5] = 3 이다.

 

동생의 위치에 도착하게 되면, visitied 배열을 따라가면서, 시작 위치에 도착할 때 까지 역순으로 출력한다.

[추가 조건]

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

코드

#숨바꼭질 4 [GOLD 4]

import sys
from collections import deque

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

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

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

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

if(n>m):
    print(n-m)
    for i in range(n,m-1,-1):
        print(i, end=' ')
    sys.exit(0)

while(queue):

    current = queue.popleft()
    if(current == m):
        break

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

now = m
order = []
while(True):
    order.append(now)
    if(now == n):
        break
    k = visited[now]
    now = k

print(len(order)-1)
for i in reversed(order):
    print(i, end=' ')

알고리즘 분류

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