[백준 / BOJ] 17071 숨바꼭질 5 (1~5)

문제

출처 : www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

이 문제는 다른 숨바꼭질 문제들과는 달리,

동생이 매 시간마다 +1 +2 +3 +4 +5 ... 의 속력으로 앞으로 질주한다.

이때, 수빈이가 동생을 찾는 가장 빠른 시간을 출력하는 문제다.

 

풀이

BFS로 풀리는 문제다.

 

우선 BFS로 수빈이가 해당 정점에 도달하는 최솟값들을 전부 갱신해주고 동생을 움직이며, 서로가 만날수있는지 봐줬다.

(동생이 수빈이를 찾는다는 느낌으로)

이때, 최솟값들을 갱신해줄경우, 실제로 만날수있는데, 안 만나고 지나가는 경우가 있어서 (예제 2번) 조건을 추가해서 풀어야했다.

 

수빈이가 A 지점에 있고, 동생이 B 지점에 있다고 하자.

수빈이가 A지점에서 B지점에 있는 동생을 만날려면, 다음조건을 만족해야한다.

 

1. 수빈이와 동생의 거리차가 홀수일때 둘의 시간차이가 홀수이며 수빈이의 시간이 동생보다 낮아야함

2. 수빈이와 동생의 거리차가 짝수일때 둘의 시간차이가 짝수이며 수빈이의 시간이 동생보다 낮아야함

 

수빈이가 현재 3번 지점에 3초만에 왔고, 동생이 3번지점에 5초에 도착한다고 하자. 수빈이는 3 -> 4 -> 3 으로 2초동안 이동해서 동생과 만날수있다. 

(홀수도 마찬가지다.)

 

위 조건만 추가해서 풀었을때 24퍼에서 계속 틀렸다고 떳다. 

 

수빈이가 A지점에 짝수초만에 도달하는 최솟값과 홀수초만에 도달하는 최솟값을 각각 갱신해줬다.

동생과 시간을 비교할때, 수빈이가 A지점에 도착하는 최솟값은 짝수, 홀수 두경우가 있을것이고, 이 둘중 한값만 저장할경우, 실제로 만날수있지만, 만나지 않는다고 보고 지나칠 경우가 있다.

 

수빈이가 3번지점에 도달할수있는 최소시간이 3초, 4초가 있다고 하자. 동생은 3번지점에 4초만에 도착한다. 이때 만약 수빈이의 도달 시간을 3초로 업데이트해놓는다면, (4초만에 만날수있지만) 짝수거리차, 홀수시간차로 판단하여 지나치게된다.

 

소스코드

숨바곡찔 5

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%201~5/main5.cpp

devxb/JJUNalgo

숨바꼭질 시리즈

 

1697 숨바꼭질 1

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%201~5/main1.cpp

devxb/JJUNalgo

12851 숨바꼭질 2

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%201~5/main2.cpp

devxb/JJUNalgo

13549 숨바꼭질 3

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%201~5/main3.cpp

devxb/JJUNalgo

13913 숨바꼭질 4

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%201~5/main4.cpp

devxb/JJUNalgo