문제 풀이

숨바꼭질 1과 비슷하지만 방법의 개수까지 세어줘야 하므로 방문 처리를 push할 때 말고 pop할 때 해줘야한다.

push할 때 방문 체크를 해준다면 다음과 같은 문제가 발생한다.
예를 들어 n=1, k=4일때, 아래와 같은 상황에서 첫번째 경우에 4를 만나 방문 체크를하고
두번째 경우에 (1 * 2)에서 4로 가려하지만 첫번째 경우에 방문 체크를 했으므로 갈 수가 없다.
1. 1 -> (1+1) -> 4
2. 1 -> (1 * 2) -> 4

그러므로 pop할 때 방문 체크를해주고, 그 뒤로는 현재 위치가 k일때마다 카운트를 세어줘서 출력하면 된다.

문제 링크

boj/12851

소스코드

PS/12851.java

  
        import java.io.*;
    import java.util.*;

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        static class Entity
        {
            int cnt;
            int pos;

            public Entity(int cnt, int pos) {
                this.cnt = cnt;
                this.pos = pos;
            }
        }
        static int []visit = new int [100001];
        static int []cnt = new int [100001];
        public static void main(String[] args) throws IOException {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            Queue<Entity> q = new LinkedList<>();
            q.add(new Entity(0,n));
            int min =987654321;
            int min_cnt =987654321;
            while(!q.isEmpty())
            {
                int cur_pos = q.peek().pos;
                int cur_cnt =  q.peek().cnt;
                q.poll();
                if(cur_pos ==k && min_cnt == 987654321) {
                    min_cnt = 1;
                    min = cur_cnt;
                }
                else if(cur_pos== k && cur_cnt == min)
                    min_cnt++;
                visit[cur_pos] = 1;
                if( cur_pos + 1 <= 100000 && visit[cur_pos +1] ==0 ) {
                    q.add(new Entity(cur_cnt + 1,cur_pos + 1));
                }
                if( cur_pos -1 >=0 && visit[cur_pos - 1] ==0 ) {
                    q.add(new Entity(cur_cnt + 1,cur_pos - 1));
                }
                if(cur_pos *2 <=100000&&visit[cur_pos * 2] == 0 ) {
                    q.add(new Entity(cur_cnt + 1,cur_pos * 2));
                }

            }
            bw.write(Integer.toString(min) + "\n" + Integer.toString(min_cnt));
            bw.flush();

        }
    }