[백준 13913번] 숨바꼭질 4 - 파이썬

문제 링크:

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

13913번: 숨바꼭질 4

 

---

풀이 유형:

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

 

풀이 과정:

이 문제는 숨바꼭질 문제를 응용한 문제로서 난이도가 조금 높아졌다. 기본 숨바꼭질 문제는 다음 링크를 참조하자.

https://data-flower.tistory.com/78

[백준 1697번] 숨바꼭질 - 파이썬

 

이 문제가 백준 1697번 숨바꼭질 문제와 다른 점은 출력 둘째 줄에 수빈이가 어떻게 이동해야 하는지 공백으로 구분해 출력해야 한다.

이는 bfs(너비 우선 탐색)의 특징을 이용해 해결할 수 있다.

 

여기서 잠깐!!

bfs는 쉽게 말해 가까운 노드부터 탐색하는 방법이다.

다음 그림을 보면 bfs 탐색은 1에서 시작 -> 2, 3, 4로 확장 -> 5, 6, 7, 8로 확장함을 알 수 있다.

너비 우선 탐색 순서

 

본론으로 돌아와 수빈이가 어떻게 이동하는지에 대한 좌표들은 bfs를 수행하는 과정에서 수빈이의 현재 위치(부모 노드)를 다음 이동할 위치(자식 노드) 인덱스에 표시해두면 된다.

자세한 풀이는 다음 풀이 코드를 참고하자.

 

풀이 코드:

check 리스트는 수빈이가 다음으로 이동할 위치 인덱스에 현재 위치를 표시해주는 역할을 한다.

move 함수는 수빈이의 이동경로를 탐색한다.

그다음 수빈이가 동생을 만났을 때 move 함수를 호출하여 수빈이의 이동 경로를 출력해주면 된다.

# 13913번 숨바꼭질 4

# 전체 크기 100000
# 1차원 좌표에서 수빈이 이동가능한 경우의 수 3가지(앞, 뒤, 순간이동)
# 동생을 찾는 가장 빠른 시간 출력 - bfs함수 이용
# 최단이동을 어떻게 하는지 출력 - move함수 이용

from collections import deque

# 수빈이 위치와 동생 위치 입력받기
n, k = map(int, input().split())
# 수빈이가 특정 위치를 방문할 때 걸리는 시간(초)을 나타내는 정보
visited = [0] * 100001
# 자식 노드가 부모 노드를 알기 위한 정보
check = [0] * 100001 # 수빈이가 동생을 만나기 전에 어떤 좌표를 이동했는지 표시하는 정보

# 동생이 있는 위치에 도달하기까지 수빈이가 어떻게 이동을 했는지 확인
def move(now):
    # 경로 탐색 시작
    data = []
    # 역으로 경로 찾기
    temp = now
    # 수빈이가 동생을 만날 때까지의 걸리는 시간만큼 반복하면서
    for _ in range(visited[now]+1):
        # 현재 위치 추가
        data.append(temp)
        # 전의 위치 받기
        temp = check[temp]
    # 거꾸로 출력
    print(' '.join(map(str, data[::-1])))


# 너비 우선 탐색 진행
def bfs():
    q = deque()
    # 수빈이의 시작 위치 받기
    q.append(n)
    while q:
        now = q.popleft()
        # 수빈이가 동생을 만났다면
        if now == k:
            # 걸린 시간 출력
            print(visited[now])
            # 어떻게 움직였는지 출력
            move(now)
            return
        # 수빈이가 이동할 수 있는 3가지 방향(뒤, 앞, 순간이동)을 차례대로 받아
        for next_node in (now-1, now+1, now*2):
            # 다음 이동할 위치가 이동가능한 좌표이며 아직 방문하지 않았다면
            if  0 <= next_node <= 100000 and visited[next_node] == 0:
                # 이동할 위치에 시간 표시
                visited[next_node] = visited[now] + 1
                # 큐에 이동할 위치를 추가
                q.append(next_node)
                # 수빈이가 지나온 위치를 알기위해 다음 이동위치에 현재 이동위치를 기록
                check[next_node] = now

# bfs 실행
bfs()

 

 

13913번 숨바꼭질 4