[알고리즘] 백준13913 숨바꼭질4 - 파이썬

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

13913번: 숨바꼭질 4

 

 

[오답 코드]

from collections import deque
from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
MAX = 100000
visited = [False] * (MAX+1)
graph = [0] * (MAX+1)

def bfs():
    q = deque()
    q.append(n)
    visited[n] = True

    while q:
        x = q.popleft()

        if x == k:
            return graph[x]
            break

        for dx in [x-1, x+1, x*2]:
            if 0<= dx<= MAX and not visited[dx]:
                q.append(dx)
                visited[dx] = True
                graph[dx] = graph[x] + 1


cnt = bfs()

b = list(filter(lambda x: graph[x] == 3, range(len(graph))))
print(b)
result = [k]
for i in range(cnt, 0, -1):
    a = list(filter(lambda x: graph[x] == i-1, range(len(graph))))
    for j in a:
        if k + 1 == j or k - 1 == j or k // 2 == j:
            result.append(j)
            k = j
            break

result.reverse()
print(*result, sep=' ')

• 틀린 이유는 시간 초과.. 예제를 입력을 기준으로 설명한다면 먼저, bfs탐색을 한다. 
• 후에 4초에서 1초까지 역으로 for문을 돌면서 filter함수를 통해 4초일 때 초가 담긴 graph배열을 탐색하면서 3초인 인덱스를 a 배열에 넣어준다. 
• 그리고 두번째 for문인 a배열에서 원소를 하나씩 빼주면서 +1, -1, %2 가 돼서 k가 된다면 저장해주고 k값을 갱신해주는 식이다.
• 내가 생각해도 되면 장땡 코드인 것 같다. 다른 사람의 풀이를 보고 좀 더 쉬운 풀이를 찾아보았다.

 

[정답 코드]

from collections import deque
from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
MAX = 100000
visited = [False] * (MAX+1)
graph = [0] * (MAX+1)
parent = [0] * (MAX+1)

def path(x):
    result = []
    temp = x
    for _ in range(graph[x]+1):
        result.append(temp)
        temp = parent[temp]
    result.reverse()
    print(*result, sep=' ')


def bfs():
    q = deque()
    q.append(n)
    visited[n] = True

    while q:
        x = q.popleft()

        if x == k:
            print(graph[x])
            path(x)

        for dx in [x-1, x+1, x*2]:
            if 0 <= dx <= MAX and not visited[dx]:
                q.append(dx)
                visited[dx] = True
                graph[dx] = graph[x] + 1
                parent[dx] = x


bfs()

• parent라는 배열을 만들어 bfs탐색 시에 이전 수빈이가 있는 위치를 저장하고 path() 함수를 통해 역추적하는 방식이다. 내가 이전에 생각했던 방식과 역으로 추적하는 방법은 같았지만 bfs탐색 시에 이전 노드를 담아준다는 점에서 큰 차이가 있는 것 같다.