BOJ 12851번 숨바꼭질2 자바(java) 풀이
문제 정리
- 수빈이는 현재 점 N에 있다. 동생은 점 K에 있다.
- 수빈이는 1초 후에 N-1, N+1, Nx2의 위치로 이동할 수 있다.
- 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후 인가??
- 가장 빠른 방법의 수도 찾아서 출력해라.
문제 풀이
bfs를 이용하면 풀 수 있는 문제입니다.
원래 bfs를 구현하게 되면 보통 최적화를 위해서 queue에 넣고 바로 방문처리를 합니다.
하지만 그것은 최적화 즉, 넣었다 뺐다 반복하지 않도록 하는 것입니다.
이 문제는 그렇게 해서는 풀 수 없습니다.
가능한 모든 개수를 세야하기 때문입니다.
반례
예를들어 1 4의 경우
(1+1)x2
(1x2)x2
위와 같이 두 가지 경우가 가능합니다
하지만 1에서 1+1로 2가 되어 visited[2]가 true가 됩니다. 그래서 queue에 다시 넣지 못하여 한 가지 밖에 나오지 않습니다
- Pair class를 만들어서 Pair형 Queue를 만들고 시작 값을 queue에 넣어주고 방문처리도 해줍니다.
- Queue에서 값을 하나 꺼냅니다. 그리고 방문 처리 합니다.
queue에 넣을때 방문처리 하지 않고 꺼낼때 방문처리 합니다.
queue에 넣을때 방문처리 하게 되면 모든 가능한 경우를 따질 수 없어 개수를 제대로 셀 수 없습니다.
ex) 1 4
- 꺼낸 값이 동생의 위치와 같은 경우 min 값과 시간을 비교합니다
min보다 꺼낸 time 값이 작다면 min 값을 update 해주고
min값과 tt 값이 같다면 같은 시간으로 갈 수 있는 다른 경우 이므로 cnt 값을 증가시킵니다.
- 이동할 수 있는 세가지 경우 모두에 대해서 방문하지 않았고 이동이 가능한 경우 queue에 넣고 방문할 수 있도록합니다.
- queue가 빌때까지 반복합니다.
문제 풀이
- 실행 시간: 236 ms
- 메모리: 93748 kb