[백준 / BOJ] 13931 숨바꼭질 4

문제

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

13913번: 숨바꼭질 4

수빈이와 동생은 숨바꼭질을 한다.

수빈는 자신의 위치에서 -1, +1, *2만큼 이동할수있다.

수빈이가 동생을 가장빨리 찾는 시간을 구하는 문제다.

 

풀이

BFS를 통해 푸는 문제였다.

 

배열을 이용해 자신의 전 위치를 체크해줘야하는데,

예를들어, 배열이 par[100005]로 선언되어있고 수빈이가 동생에게 가는 경로가 5 10 20 40 이라면,

par[40] = 20

par[20] = 10

par[10] = 5

par[5] = -1(시작지점을 -1로 표시했다.)

이런식으로 저장해 놓는다.

하지만, 수빈이의 위치에서 동생의 위치까지 갈수있는 경로가 여러가지 나올수 있으므로 pair를 사용해서 저장해줘야한다.

 

수빈이가 동생에게 가는 최소시간 경로가

5(0초) 10(1초) 20(2초) 40(3초) 인데, 어떤 경우에 2초에 지점 19에서 20으로 갔다고 생각하면,

par[40] = 20

par[20] = 10 -> par[20] = 19

par[10] = 5

par[5] = -1

위 처럼 바뀌게 되고, 출력경로는  0 19 20 40이 출력된다..

 

위를 방지하기 위해,

pair<int,int> par[100005]; 

이런식으로 배열을 만들고 

par[idx] = {도착 시간, 부모 idx};

위와같이 저장한다.

par[idx]에 저장되어있는 도착 시간보다 오래걸렸다면 업데이트해주지 않고 아니라면 경로를 업데이트해준다.

 

위 처럼 선언하는게 항상 성립하는 이유를 예를들어 설명하면,

수빈이가 동생에게 가는 최소시간 경로를 5 -> 10 -> 20 -> 40 이라고 하자

수빈이는 동생에게 가기위해서 10 지점을 지나가야한다. 그렇다면 10지점에 가장 최소한으로 도착하는 경로가 항상 최소시간 경로가 되는것이다.

 

코드를짤때 수빈이가 이동할수있는 최대거리는 100000이고 최소거리는 0이다. 이 사이의 거리를 초과해서 지나가지않도록 주의하자.

동생의 위치가 100000일때, 수빈이가 100002로 갔다가 100000으로 갈수없다. (최대이동거리인 100000을 벗어났기때문)

소스코드

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

devxb/JJUNalgo