Algorithm/백준

[백준 알고리즘] 13549번: 숨바꼭질 3 (Python, BFS)

에릭 Kim 2023. 10. 18. 18:35
반응형

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

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

소스코드

 

 

풀이

★ 수빈이가 이동할 수 있는 경우를 다 탐색한 후, 그 이후에 가지를 쳐서 뻗어나가는 형식의 전형적인 BFS 문제인 거 같습니다 ! 

 

★ 수빈이가 이동할 수 있는 방법은 순간이동과 걷기가 있습니다 ! 이 떄 순간이동을 하는 경우는 초가 증가하지 않지만 걷는 경우에는 초를 1씩 증가시켜줍니다.

 

★ BFS 안의 for문을 돌 때 순간이동을 하는 경우 먼저 확인해줘야 합니다. 그 이유는 

예를 들어, 1과 2가 n,k로 주어진 경우

 

걷는 경우부터 생각하게 된다면 1에서 2로 가는 데 걸린 시간은 1초가 된 뒤 함수를 종료시킵니다.

하지만 순간 이동을 먼저 하는 경우 2*n만큼 이동하기에 0초가 걸립니다 ! 

반응형