BOJ
[BOJ][Python] 백준 12851번 - 숨바꼭질 2
송댕
2022. 1. 15. 10:20
728x90
문제 링크: https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
문제 풀이
기본적인 BFS에 경우의 수를 카운트를 합친거 같지만 숨바꼭질 1과 다르게 push때 방문을 적용하는게 아니라 pop때 해줘야 한다.
예를 들어서 1에서 4까지 간다고 했을 때, 1에서 2로 가는 경우가 두 가지가 있다. +1 혹은 *2인데, +1에서 이미 방문을 해버린 거로 체크한다면 *2의 연산이 안되기 때문이다. 그 외에는 간단하게 구현해주면 답이 나온다.
코드
728x90