[BOJ/백준] 13913 - 숨바꼭질 4 파이썬/Python3

[BOJ/백준] 13913 - 숨바꼭질 4 파이썬/Python3 

---

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

13913번: 숨바꼭질 4

 

숨바꼭질 시리즈 중에 4번째

공통된문제: 수빈이의 최소 소요 시간

추가된 요구 조건: 수빈이의 탐색 경로를 함께 제시

수빈이가 탐색한 경로를 어떻게 출력해야 될지를 고민했던 문제

 

[문제해결방식]

1. 수빈의 최소 이동 시간

 1) 수빈이는 3가지 선택지가 있다.

 현재 위치를 기준으로 -1칸,  +1칸, 현재 위치 * 2칸을 방문할 수 있다.

 2) 각각의 위치에 대해 이동 시간을 저장해서 동생의 위치를 방문할 때까지 탐색

 3) bfs 알고리즘을 활용해서 방문 위치에 대한 이동 시간을 저장하는 cost 배열을 갱신

 

2. 수빈의 탐색 경로

 1) 트리의 방식으로 문제 해결

 2) move 배열을 만들어 현재 노드의 index 값에 부모 노드를 저장

 부모 노드: 현재 노드 직전에 출발한 노드의 위치

 수빈이가 동생의 위치를 찾은 경우 path 함수를 호출

 3) 동생의 도착 위치에서 수빈이의 처음 시작 위치까지를 역추적해서 경로를 저장

 4) 현재 저장된 경로는 도착 노드에서 출발 노드순으로 저장되어 있기 때문에 역순으로 출력

 

 

해결 코드

from collections import deque
# 그래프의 크기
row = 100001


def check(a):
    if a < 0 or a > row-1:
        return True
    return False


def path(x):
    # 경로를 저장할 배열
    arr = []
    # 현재 수빈이의 위치
    temp = x
    # 도착 노드에서 출발 노드를 역추적하는 방식으로 경로를 arr 배열에 저장
    for _ in range(cost[x] + 1):
        arr.append(temp)
        temp = move[temp]
    # 현재 arr은 도착 경로에서 출발 경로를 역순으로 추적해서 저장된 상태, 슬라이싱 활용해 역순으로 출력
    print(' '.join(map(str, arr[::-1])))


def bfs():
    q = deque()
    q.append(N)
    while q:
        # 현재 수빈이의 위치 x
        x = q.popleft()
        # 수빈이의 위치와 동생의 위치 K와 일치할 경우
        if x == K:
            # 수빈이가 동생을 찾는 가장 빠른 시간을 출력
            print(cost[x])
            # 가장 빠른 시간일때의 경로 출력
            path(x)
            # bfs 함수 종료
            return
        # 수빈이의 순간이동 방향 3가지
        for i in (x - 1, x + 1, 2 * x):
            # 범위 체크
            if check(i):
                continue

            # 처음 방문한 경우
            if cost[i] == 0:
                q.append(i)
                # 방문한 위치에 소요 시간을 저장
                cost[i] = cost[x] + 1
                # 현재 수빈이의 위치에 수빈이가 직전에 방문한 노드를 저장
                move[i] = x


# 수빈이가 있는 위치 n, 동생이 있는 위치 k
N, K = map(int, input().split())
# 수빈이가 방문한 위치에서 걸리는 시간을 저장하는 배열
cost = [0] * row
# 수빈이가 방문한 위치에서 이전에 어떤 노드를 지났는지 저장하는 배열
move = [0] * row
# 수빈이의 순간이동 시작
bfs()