-
[백준] 13913번 문제 (숨바꼭질 4) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 10. 14. 13:55
https://www.acmicpc.net/problem/13913
from collections import deque, defaultdict import sys input = sys.stdin.readline n, k = map(int, input().split()) visited = [False] * 100001 path = defaultdict(list) q = deque() q.append([n, 0]) while q: cur, count = q.popleft() visited[cur] = True path[count].append(cur) if cur == k: print(count) break if 0 <= cur + 1 <= 100000 and not visited[cur + 1]: q.append([cur + 1, count + 1]) if 0 <= cur - 1 <= 100000 and not visited[cur - 1]: q.append([cur - 1, count + 1]) if 0 <= cur * 2 <= 100000 and not visited[cur * 2]: q.append([cur * 2, count + 1]) result = [] result.append(k) temp = k for i in range(count - 1, 0, -1): if temp / 2 in path[i]: result.append(int(temp / 2)) temp = int(temp / 2) elif temp - 1 in path[i]: result.append(temp - 1) temp = temp - 1 elif temp + 1 in path[i]: result.append(temp + 1) temp = temp + 1 result.append(n) if n == k: print(k) else: print(" ".join(map(str, result[::-1])))
bfs 문제다.
우선 bfs를 통해 '수빈이가 동생을 찾는 가장 빠른 시간' 을 구한다.
그와 동시에 path에 수빈이가 이동한 경로를 저장해놓는다.
그리고 동생의 위치에서 초기 수빈이의 위치까지 path에서 값을 적절히 찾아 출력한다.
'Problem Solving > Baekjoon' 카테고리의 다른 글
[백준] 14226번 문제 (이모티콘) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 13549번 문제 (숨바꼭질 3) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 12851번 문제 (숨바꼭질 2) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 1743번 문제 (음식물 피하기) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 1806번 문제 (부분합) 파이썬(Python) 풀이 (0) 2021.10.14