백준 13913 숨바꼭질4 파이썬

문제링크

https://www.acmicpc.net/problem/13913

그래프로 풀면 어떨까?

어떻게 해야하나 싶었는데 BFS, DFS로 접근하면 되지않을까? 에 대한 고민을 했고
다행히 완탐처럼 그래프 돌려서 풀었는데 성공했다

빠르게 연산된경우가, 늦게 연산된 경우보다 무조건 길이가 짧을까?

생각하는게 두가지가 있는데
단순 +1 -1만 사용해서 증감한 경우와 *2 +1 -1 모두를 사용해서 증감을 한경우 중에
특정한 숫자는 무조건적으로 연산횟수가 빠른게 먼저나올까? 에 대한 고민이었다

정답은 옳다. 나는 BFS로 풀었는데, 이때 특정값을 기준으로 +1 -1 *2 값에 접근하는거고
빨리 나온 숫자는 연산횟수가 짧아서, 길이가 짧다. 방문처리를 따로 확인하는 변수가 있어야한다.

경로를 저장해야한다

문제에서 원하는 요구사항을 보면 ‘어떻게 움직였는지’ 를 출력해야한다. BFS 에 [경로] 를 함께 넣어서 돌릴까 했는데
이러면 시간초과날뿐더러, 모든 경로에 대한 움직임을 다 넣어줘야해서 무조건 터진다.
따라서 이 문제는 BFS+백트래킹으로 푸는게 낫다

코드설명

while Q :
    num = Q.popleft()

    #종료조건
    if num == K :
        break

    #진행조건
    else :
        for idx in (num-1, num+1, num*2) : #3가지 경우
            if (0<=idx<MAX) and (visited[idx] == -1) : #맵 밖을 벗어나지않고, 방문처리 한 경험이 없는거
                visited[idx] = 0
                moved[idx] = num
                Q.append(idx)

• 원하는 숫자가 나와서 종료하기 전까지, -1 +1 *2 값에 대해서
  범위 내에 있는값인지, 방문한적이 없는지 를 검사한다

#백트래킹
while True :

    #종료조건 #시작값에 도착했을떄
    if i == -1:
        # print(result)
        result.reverse()
        print(len(result) -1)
        print(*result)
        break

    #진행조건
    else :
        result.append(i)
        i = moved[i]

• 원하는 숫자에 도착했으면 경로를 백트래킹한다
  result 에 지나온 숫자를 모두 넣고, 출력할땐 reverse() 해서 출력한다

코드(전체)

#testcase1
# N, K = 5, 17
#testcase2
# N, K = 0, 5

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

MAX = 100001
visited = [-1] * MAX
moved = [-1] * MAX

from collections import deque
Q = deque()
Q.append(N)

visited[N] = 0 #방문처리
moved[N] = -1 #현재 값이 어디서 왔는지 기록

while Q :
    num = Q.popleft()

    #종료조건
    if num == K :
        break

    #진행조건
    else :
        for idx in (num-1, num+1, num*2) : #3가지 경우
            if (0<=idx<MAX) and (visited[idx] == -1) : #맵 밖을 벗어나지않고, 방문처리 한 경험이 없는거
                visited[idx] = 0
                moved[idx] = num
                Q.append(idx)

#초기값
i = moved[K]
result = [K]

#백트래킹
while True :

    #종료조건 #시작값에 도착했을떄
    if i == -1:
        # print(result)
        result.reverse()
        print(len(result) -1)
        print(*result)
        break

    #진행조건
    else :
        result.append(i)
        i = moved[i]