새소식

알고리즘 문제풀이/BOJ

[BFS] 백준 12851번 숨바꼭질2 자바(java) 풀이

  • -

BOJ 12851번 숨바꼭질2 자바(java) 풀이

문제 정리

  1. 수빈이는 현재 점 N에 있다. 동생은 점 K에 있다.
  2. 수빈이는 1초 후에 N-1, N+1, Nx2의 위치로 이동할 수 있다.
  3. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후 인가??
  4. 가장 빠른 방법의 수도 찾아서 출력해라.


문제 풀이

bfs를 이용하면 풀 수 있는 문제입니다.
원래 bfs를 구현하게 되면 보통 최적화를 위해서 queue에 넣고 바로 방문처리를 합니다.
하지만 그것은 최적화 즉, 넣었다 뺐다 반복하지 않도록 하는 것입니다.
이 문제는 그렇게 해서는 풀 수 없습니다.
가능한 모든 개수를 세야하기 때문입니다.

반례
예를들어 1 4의 경우
(1+1)x2
(1x2)x2
위와 같이 두 가지 경우가 가능합니다
하지만 1에서 1+1로 2가 되어 visited[2]가 true가 됩니다. 그래서 queue에 다시 넣지 못하여 한 가지 밖에 나오지 않습니다

  1. Pair class를 만들어서 Pair형 Queue를 만들고 시작 값을 queue에 넣어주고 방문처리도 해줍니다.
  2. Queue에서 값을 하나 꺼냅니다. 그리고 방문 처리 합니다.
    queue에 넣을때 방문처리 하지 않고 꺼낼때 방문처리 합니다.
    queue에 넣을때 방문처리 하게 되면 모든 가능한 경우를 따질 수 없어 개수를 제대로 셀 수 없습니다.
    ex) 1 4
  3. 꺼낸 값이 동생의 위치와 같은 경우 min 값과 시간을 비교합니다
    min보다 꺼낸 time 값이 작다면 min 값을 update 해주고
    min값과 tt 값이 같다면 같은 시간으로 갈 수 있는 다른 경우 이므로 cnt 값을 증가시킵니다.
  4. 이동할 수 있는 세가지 경우 모두에 대해서 방문하지 않았고 이동이 가능한 경우 queue에 넣고 방문할 수 있도록합니다.
  5. queue가 빌때까지 반복합니다.


문제 풀이


- 실행 시간: 236 ms
- 메모리: 93748 kb
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.