[c++] 백준 숨바꼭질 4(13913), bfs, 반례모음

문제 https://www.acmicpc.net/problem/13913

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

반례모음

24 300 10 24 23 22 21 20 19 38 76 75 150 300	100 1 99 100~1까지 순서대로
2 1024 9 2 4 8 16 32 64 128 256 512 1024	5 4 1 5 4
0 0 0 0	0 1 1 0 1
0 4 3 0 1 2 4	4 4 0 4
4 7 2 4 8 7	1 0 1 1 0
1 5 3 1 2 4 5	1 100000 21 1 2 3 6 12 24 48 49 98 196 195 390 780 781 1562 3124 3125 6250 12500 25000 50000 100000

 

풀이

• 문제의 핵심은 이동경로를 저장해야 합니다. 
  수빈이가 동생을 최단거리로 찾았을 때, 방문했던 점의 위치를 출력합니다.
  이를 위해, 수빈이는 이동시에 현재까지 방문한 점들의 위치정보를 계속 저장하고 있어야 하며, 새로운 경로가 할당될 시에도 기존에 저장한 점들 경로 + 새로운 점 경로, 이런식으로 저장.
• 일반적인 BFS를 사용하되, 현재 위치에서 X-1, X+1과 X*2의 위치를 탐색하고, 동생이 없을시 해당 좌표를 다시 탐색합니다.
  이를 위해, 큐 구조에 STL <pair>를 사용해서 다음에 방문할 좌표(int x)와 현재까지 방문한 좌표들(vector<int>)을 계속 쌓아줍니다.
• 단, 예외처리 및 주의사항이 있습니다.
  1. 수빈이와 동생의 시작위치는 0일 수도 있습니다(둘 다 0일수도, 둘 중 한명만 0일수도) 
      따라서, 둘다 0이거나, 둘의 위치가 같을 때의 예외처리가 필요합니다.
  2. 수빈이의 위치가 동생의 위치보다 멀수도 있습니다. 다시말해, 동생 < 수빈.
      이럴 경우, 수빈이는 X-1로만 이동해서 동생을 만나야 하므로 예외처리 해줍니다.
  3. 수빈 < 동생이라고 해서 무조건 X+1, X*2만 해야 한다고 생각하면 안됩니다.
      때로는 X-1후에 X*2를 수행했을 때 최단경로일 수 있습니다.
  
  
• https://forward-gradually.tistory.com/43

[c++] <STL> pair 사용법

https://forward-gradually.tistory.com/9

c++ STL <vector> 정리

 

코드

알게 된 점

• 문제 조건에 따른 예외처리 생각
• 때로는, 수빈이가 X-1을 한 후에 X*2를 했을 때, 더 빠른 경로를 찾을 수 있음.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%884(13913).cpp