-
1679 숨바꼭질알고리즘/백준 문제 2020. 5. 16. 13:43
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가
www.acmicpc.net
이 문제 역시 최소시간(최단거리)를 구하는 문제이기 때문에 BFS를 이용해서 풀었다.
큐에 들어갈 다음 경로는 문제에 나와 있듯이 3가지가 있다.
- x+1
- x-1
- x*2
이전 BFS문제들과 같은 방식인데, 다른 문제에서 동서남북으로 움직이던 것을 이 문제에서는 위의 3 가지 경우로 움직이면 되고
일직선 상의 경로니까 1차원 배열을 사용했다. 때문에 오히려 쉬웠다.
아! 그리고 문제를 제출했을때 런타임에러가 났었는데 그 이유는 찾는 대상이 기준점보다 앞에 있을 경우를 고려하지 않았다.
무슨 말이냐면, 문제의 예시는 수빈이(x)가 5 동생(y)이 17에 있을 경우고
문제를 해결해나가는 과정에서 x < y 인 상황만 고려한 것이다.
하지만 x > y인 경우도 있다. (수빈이가 5, 동생이 1 등등.. x > y인 경우 (x-1) 로만 움직인다.)
사실 이 문제는 BFS로 푼다는 사실을 알고 있었기 때문에 쉬웠다.
알면서도 이게 내가 아는 그 방식과 같을까 라는 생각을 했는데, 아무튼 명심해야 할 것은
최단거리 = 갔던 길을 되돌아가지 않아야 함
때문에 이 문제에서도 한번 방문한 길은 되돌아가지 않도록 표시를 해주어야 한다.