BOJ(숨바꼭질4)(19313)

작성일 | In

BFS

  • BFS로 문제를 푼다는 것은 문제 상황 => 그래프로 나타냄
  • 이 때, 그래프의 모든 간선의 가중치가 1이 나오는 것을 확인해야 한다.
  • 그래프의 간선 가중치가 모두 1이라면, 최단 거리를 구하는 알고리즘이 BFS이기 때문에, BFS를 시작하면 된다.

숨바꼭질 4

  • 수빈이의 위치 : N
  • 동생의 위치 : K
  • 동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제

  • 수빈이가 할 수 있는 행동 (위치 : X)

    1. 걷기 X+1 또는 X-1로 이동 (1초)
    1. 순간이동 2*X로 이동 (1초)
  • X가 갈수 있는건 X+1, X-1, 2X
  • 즉 N->K로 가는 가장 빠른 시간을 구하는 것.
  • 가중치가 1이라고 생각할 수 있다.
  • 그럼 BFS로 풀 수 있다.

  • 이동하는 방법도 구하라고 했으니까. 이동하는 방법도 어떻게 구하는지 알아보자.

  • now -> next로 갔다고 한다면
  • next를 방문하지 않았으면, 무조건 방문해야 한다.

  • 그때 next까지의 거리가 now+1이다.

  • 이렇게 해서 문제를 풀면 가장 빠른 시간은 구할 수 있지만, 이동하는 방법은 구할 수 없다.
  • 이동하는 방법을 구하려면 next란 곳에 어떻게 왔는지를 기록해야한다.
  • next를 어디서 왔는지 알기 위해서 from이란 배열을 만들고, form은 now에서 왔다.고 표시해주면 된다.
  • 어떤 정점을 어디에서 왔는지 다 기록할 수 있게 된다.
  • 이제 이 정보를 이용해서, 원래의 경로를 구하는 과정이다.
  • from에는 정보가 역순으로 저장이 된다.
  • 우리가 필요한 것은 A->B->C->D->E가 필요하다.
  • 따라서 from을 역순으로 구한다음에 다시 뒤집어 주는게 필요하다.
  • 재귀함수를 이용하는 방법도 있고
  • 또 다른 방식은 방문한 정점을 역순으로 출력 -> stack을 사용
  • 굳이 스택을 쓸 필요는 없고 배열을 만든 다음에, 뒤에서 부터 출력하거나 뒤집은 다음에 출력해도 된다.
from collections import deque
import sys
MAX = 200000
sys.setrecursionlimit(MAX)
check = [False] * MAX
dist = [-1] * MAX
via = [-1] * MAX
n,m = map(int,input().split())
check[n] = True
dist[n] = 0
q = deque()
q.append(n)
while q:
    now = q.popleft()
    if now-1 >= 0 and not check[now-1]:
        q.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
        via[now-1] = now
    if now+1 < MAX and not check[now+1]:
        q.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
        via[now+1] = now
    if now*2 < MAX and not check[now*2]:
        q.append(now*2)
        check[now*2] = True
        dist[now*2] = dist[now] + 1
        via[now*2] = now
print(dist[m])
def go(n, m):
    if n != m:
        go(n, via[m])
    print(m, end=' ')
go(n, m)

참고자료 codeplus

0%