[c++] 백준 숨바꼭질(1679), BFS, 반례모음

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

• 수빈이(N)이 동생(K)를 찾는 가장 빠른 시간 출력
• 수빈이는 현재 위치(X)에서 3가지 동작(X+1, X-1, 2*X) 가능
• 5 17 -> 4출력(5-10-9-18-17)

 

풀이

• 1차원에서 수빈이의 이동 가능한 모든 방향을 탐색, 동생을 찾을 때까지 계속한다.
• 마치 가능한 모든 경우의 수를 탐색하는 것과 같음.
• 1차원 벡터(배열)의 map을 만들고, 수빈이의 시작지점에 1의 값을 넣고, 다음 이동 배열 값에 현재 위치의 값+1을 해주며 확산한다. 
• 동생을 찾을 시 종료.
• 예외 처리
  - 이전에 방문한 좌표는 패스
  - 배열의 일정 크기를 넘으면 패스
  - 0 0을 받을시 0을 출력
  - 기타 반례모음 아래에.

 

반례모음

입력 6 11 정답 (6-12-11) 2	input: 0 1 answer: 1	input: 1 15 answer: 5	1 100000 21	1 0 1	10 40 2
0 0 0	5 0 5	10007 98767 2343	15964 89498 4781	5 35 5	3482 45592 637

 

코드

 

알게 된 점

• 예외처리! 반례!

 

git 코드

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