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

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

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

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

 

반례모음

10000 0 10000

2 7 1

1 17 1

4 6 1

0 1 1

0 3 2

0 0 0

1 32 0

3 22 1

5 7 2

1 10000 3

1 100000 5

 

풀이

• 순간이동 할 시에는 0초가 소요되므로, 현재 위치에서 순간이동으로 좌표들을 먼저 구해야 합니다.
  - 단, 다음과 같은 조건을 고려
    1. 순간이동으로 동생을 찾을 경우
    2. 순간이동 했을 시, 동생의 위치보다 한 참 머리 떨어진 경우 제외(동생위치 *2만큼 설정했습니다)
    3. 순간이동 된 좌표가 이미 방문한 경우 제외
  - 조건을 제외한 순간이동 된 좌표들은 큐에 쌓아줍니다. 
• 큐에 쌓은 좌표들을 하나씩 방문하여 bfs로 인접한 X-1, X+1를 방문하여 동생을 찾고, 방문 여부 체크합니다.
  또한, 새로 방문한 좌표들에서 각각 순간이동을 위와 동일하게 수행합니다. 
• 가장 먼저 동생을 찾았을 때, 걸린 시간을 구하면 됩니다.
• 단, 문제에서 수빈과 동생의 시작좌표가 0일 수도 있으므로, 이를 고려하여 조건처리 해주어야 합니다.
  뿐만 아니라 수빈이 동생보다 더 뒤쪽에 있을 경우도 고려합니다.

 

코드

• 큐 구조를 2개 생성
  Q1 : bfs로 인접한 좌표들을 쌓고,
  Q2 : Q1에서 나온 하나의 좌표를 순간이동을 반복하여 좌표들을 쌓고, 동생 여부 체크, Q1에 해당 좌표들도 쌓아줌
• 적절한 조건문과, 방문여부체크
• 방문하는 곳이 음수(-)로 넘어가지 않도록 주의해야 합니다.

 

알게 된 점

• 큐에 쌓아서 bfs를 수행할 때에는 우선순위를 잘 고려해야 한다.
• 이 문제에서는 시간(초)에 따른 우선순위를 고려하여, 같은 시간상에서 탐색을 모두 마치도록 수행해야 한다.

 

git 코드

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