백준(BOJ) 13913 숨바꼭질4 (Python3)

 

문제 링크

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

13913번: 숨바꼭질 4

 

 

★ 문제 해결에 대한 접근

 

1. [현재 위치 = 수빈이 위치 (N)],   [도착 위치 = 동생의 위치 (K)]가 주어지고 빠른 시간(최단거리)을 계산.

이는 특정 정점에 도달하는 방법 중 가장 빠르게 도착할 수 있는 방법을 찾아내는 BFS (너비 우선 탐색) 예상.

 

2. 출력을 위해서 도착 위치까지 도달할 수 있는 경로 중 하나의 Case를 출력.

"스페셜 저지" = 최단 거리로 도달할 수 있는 방법은 1개 이상일 수 있음을 의미

이전에 도착한 노드(정점)의 위치를 기억할 수 있는 자료구조가 필요.

 

 

예시 입력으로 구성한 BFS 결과 도출 과정

 

BFS는 도착한 노드(정점)가 곧 가장 빠른 방법임을 보장할 수 있습니다.

 

가지는 3개로 뻗어나가게 됩니다.

• 현재 위치에서 +1
• 현재 위치에서 -1
• 현재 위치에서 x2

가지가 뻗어나갈 수 있는 조건(가지치기)은 2가지로 고려할 수 있습니다.

• 도달할 수 있는 노드(정점)인지.  문제에서 노드로 가능한 범위는 닫힌 구간으로 [0, 100000]입니다.
• 이미 도달했던 노드(정점)인지. 이미 한 번 방문한 노드라면 더 이상 갈 필요가 없다.

 

★ 이전까지 방문했던 경로를 담아내는 방법

출력에 필요한 경로 기록을 저장하는 방법으로 2가지를 생각했었습니다.

1. BFS의 Queue로 담기는 인자에 "문자열" 방식으로 노드 정보를 추가하기.
2. 별도의 연결리스트를 만들고, 도달하기 이전 노드의 값을 저장하기.

 

※ 문자열을 인자에 추가하는 방식.

방문한 노드의 정보를 문자열로 저장해 도착지에 다다르면 한 번에 출력

 

 문자열을 인자에 담아 다음 Queue의 노드로 사용하는 방식으로 해결 가능합니다.

단, 가지가 생길 때마다 문자열 데이터를 생성하고 합치는 과정이 반복되므로 처리 시간이 오래 거립니다.

그래서 아슬아슬하게 정답 처리가 될 수 있는 방식입니다.

 

 

 

※ 연결 리스트를 구성해 이전 노드의 값을 저장하는 방식.

연결 리스트를 이용해 노드 정보 저장하는 구조

 

연결 리스트를 이용하면 도착지에 다다랐을 때, 그 노드에 해당하는 인덱스 위치의 값을 뽑아가며 노드의 경로를 출력할 수 있습니다.

 

위의 이미지를 예시로, 17번 노드에 도착한다고 가정하겠습니다.

 - 17번 노드에 가기 전의 위치는 노드 16입니다.  따라서 리스트의 17번 노드에는 16이 저장되어 있습니다.

 - 16번 노드에 가기 전의 위치는 노드   8입니다.  따라서 리스트의 16번 노드에는   8이 저장되어 있습니다.

 -   8번 노드에 가기 전의 위치는 노드   4입니다.  따라서 리스트의   8번 노드에는    4가 저장되어 있습니다.

...

이런 방식으로 연결된 노드들을 추적하면 처음 시작했던 노드에 도착할 수 있습니다.

즉, 시작 위치부터 도착 위치까지의 경로를 뽑아낼 수 있게 되는 것입니다.

 

 

 

구현 코드

from collections import deque
N,K=map(int,input().split())

# 초기화 값은 노드가 가능한 범위 (0~100000)에 벗어나는 값으로 명확하게 구분
dist=[-1]*100001   #해당 노드에 도착하기까지의 거리 값 저장
nodes=[-1]*100001  #해당 노드에 도착하기 이전의 노드 값 저장

dist[N]=0  # 첫 시작 노드의 시간은 0
q=deque()
q.append(N)
while q:
    pos= q.popleft()

    if pos==K:
        print(dist[pos])  # 도착하기 까지의 시간
        ret = []
        ret.append(K)
        # 연결 리스트에 저장된 도착지까지의 경로를 뽑아 저장
        for _ in range(dist[pos]):
            ret.append(nodes[K])
            K = nodes[K]

        # 출력은 역순으로 일어나야 한다. (경로를 역추적했기 때문)
        print(' '.join(map(str,ret[::-1])))
        break

    for nx in [(pos-1), (pos+1), (pos*2)]:
        if 0<= nx <= 100000 and dist[nx] == -1:
            dist[nx] = dist[pos]+1
            nodes[nx] = pos
            q.append(nx)

 

- 끝 -