[백준/Python] - 13913번 숨바꼭질4

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

📜제출코드 

from collections import deque

N, K = map(int ,input().split())

dot_list = [0] * 100001

visited = [0] * 100001

q = deque()

q.append(N)

def path(current):

    arr = []

    temp = current

    for _ in range(dot_list[current] + 1):

        arr.append(temp)

        temp = visited[temp]

    print(' '.join(map(str, arr[::-1])))

while q:

    current = q.popleft()

    if current == K:

        print(dot_list[current])

        path(current)

        break

    for i in (current-1, current+1, current*2):

        if 0<= i <= 100000 and dot_list[i] == 0:

            dot_list[i] = dot_list[current] + 1

            q.append(i)

            # 현재 노드에서 이전 노드에서 온 값을 넣어줌

            visited[i] = current

 

📜풀이

숨바꼭질 문제에서 방문 리스트를 만들어서 추가로 출력하는 문제이다.

다른 부분은 모두 동일한데 

방문 리스트를 저장해줘야한다.

 

def path(current):

    arr = []

    temp = current

    for _ in range(dot_list[current] + 1):

        arr.append(temp)

        temp = visited[temp]

    print(' '.join(map(str, arr[::-1])))

이부분이 추가되는 것이다.

 

1.  현재 노드에서 이전 노드에서 온 값을 넣어줌

 

    for i in (current-1, current+1, current*2):

        if 0<= i <= 100000 and dot_list[i] == 0:

            dot_list[i] = dot_list[current] + 1

            q.append(i)

            # 현재 노드에서 이전 노드에서 온 값을 넣어줌

            visited[i] = current

조건문을 만족했을 때 다음 정점으로 이동하면서 이동한 정점에 이전 정점의 값을 넣어준다. 

그럼 해당 정점이 어디서 왔는지 알 수 있는 것이다.

 

2. 기저조건 만족하면 visited한 정점을 구하기 위한 path함수

def path(current):

    arr = []

    temp = current

    for _ in range(dot_list[current] + 1):

        arr.append(temp)

        temp = visited[temp]

첫번째 정점도 출력을 해줘야되니까 걸린 시간 +1을 해줘서 첫 정점도 출력하게 해준다.

 

예제로 예시를 들면

5 17이다.

 

5에서 17까지 가는데 필요한 방문 정점은

5 -> 4 -> 8 -> 16 -> 17

이다.

그럼 17부터 시작해서 

        arr.append(temp)

        temp = visited[temp]

arr에는 현재 노드를 넣어주고

어디서 왔는지 알기위해서 visited에는 이전에 온 노드를 넣어줬다.

visited[temp]는 visited[17]이기때문에 16을 temp에 저장해줄 것이다.

dot_list[current] + 1 의 값은 5이기때문에 0부터 4까지 5번 for루프를 돌아준다.

• arr = [17, ]                              temp = visited[17] --> 16
• arr = [17, 16]                           temp = visited[16] --> 8
• arr = [17, 16, 8]                       temp = visited[8] --> 4
• arr = [17, 16, 8, 4]                   temp = visited[4] --> 5
• arr = [17, 16, 8, 4, 5]               temp = visited[5]

이런식으로 arr에 추가되는데 슬라이싱 이용해서 역으로 출력만 해주면 된다.

 

📜회고

BFS에 방문점만 추가한 것인데 

구글링 해서 풀었다... 이제 BFS에 방문 정점도 생각을 하면서 풀어봐야겠다