백준 13913: 숨바꼭질 4 (파이썬)

11517 단어 psps


정답코드

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

arr = []
visited = [False for i in range(150001)]
answer = [0 , []]

def bfs(start, depth, route):
    global answer
    arr.append([start, depth, route])
    visited[start] = True

    while len(arr) > 0:
        curr = arr[0][0]
        d = arr[0][1]
        r = arr[0][2]
        del arr[0]

        next1, next2, next3 = curr * 2, curr + 1, curr - 1

        if next1 == K or next2 == K or next3 == K:
            answer[0] = d + 1
            answer[1] = r
            answer[1].append(K)
            break

        if next1 < 150001 and not visited[next1]:
            visited[next1] = True
            temp = r[:]
            temp.append(next1)
            arr.append([next1, d + 1, temp])
        if next2 < 150001 and not visited[next2]:
            visited[next2] = True
            temp = r[:]
            temp.append(next2)
            arr.append([next2, d + 1, temp])
        if next3 >= 0 and not visited[next3]:
            visited[next3] = True
            temp = r[:]
            temp.append(next3)
            arr.append([next3, d + 1, temp])


if N!= K:
    if N > K:
        answer[0] = N - K
        for i in range(N, K - 1, -1):
            answer[1].append(i)
    else:
        bfs(N, 0, [N])
else:
    answer[1].append(N)

print(answer[0])
for i in answer[1]:
    print(i,end=' ')

문제유형

BFS

좋은 웹페이지 즐겨찾기