-
[백준] 12851번 문제 (숨바꼭질 2) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 10. 14. 13:49
https://www.acmicpc.net/problem/12851
from collections import deque, defaultdict import sys input = sys.stdin.readline n, k = map(int, input().split()) visited = [False] * 100001 counted = defaultdict(int) q = deque() q.append([n, 0]) while q: cur, count = q.popleft() visited[cur] = True if cur == k: counted[count] += 1 else: 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]) for key in counted.keys(): print(key) print(counted[key]) sys.exit(0)
bfs 문제다.
bfs를 통해 수빈이가 이동할 수 있는 경우로 동생 위치에 도달할때까지 모두 탐색한다.
동시에 count 를 1씩 증가시키며 '수빈이가 동생을 찾는 가장 빠른 시간'을 구한다.
'가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수'를 구하기 위해 필자 같은 경우는 우선 counted라는 딕셔너리를 선언했다.
그리고 수빈이가 동생 위치에 도달했을 때, 그 떄까지의 걸린 시간을 key 값으로 value에 +=1 을 해주며 저장해놓는다.
그러면 자연스럽게 counted에 저장된 값들 중 첫번째 값이 '가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수' 가 된다.
'Problem Solving > Baekjoon' 카테고리의 다른 글
[백준] 13549번 문제 (숨바꼭질 3) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 13913번 문제 (숨바꼭질 4) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 1743번 문제 (음식물 피하기) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 1806번 문제 (부분합) 파이썬(Python) 풀이 (0) 2021.10.14 [백준] 14719번 문제 (빗물) 파이썬(Python) 풀이 (0) 2021.10.14