백준 13913 숨바꼭질4 java

만약 제대로 작성한거 같은데 시간이 너무 느리다면... 시간낭비하지말고 넘어가시길 바란다. 바로 다음줄에 나오겠지만 그냥 예외처리 해주면 빠르게 나올 뿐이다.

bfs로 3가지 경우( -1, 1, x2 ) 를 각각 큐에 넣고 돌린다.

처음에 2700ms가 나오길래.. 내가 뭐 잘못 넣었나 한참 찾았으나

100000 -> 1처럼 숫자가 작아질때는 무조건 -1만 해주므로 이걸 예외처리처럼 빼서 작성하면 시간이 빨라질 뿐이었다.

package com.ll.boj.bfs.p13913;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {
    static final int[] dx = new int[]{0, -1, 1};
    static int k;
    static int n;

    static Deque<Integer> stack = new ArrayDeque<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        int[][] field = new int[100001][2];
        for (int i = 0; i <= 100000; i++) {
            Arrays.fill(field[i], -1);
        }
        br.close();

		//k보다 n이 더 작은경우만 예외처리
        if(k < n){
            field[k][0] = n - k;
            while(k!=n){
                stack.offer(n);
                n--;
            }
            stack.offer(n);

        } else{
            bfs(field);
            push(field);
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
            sb.append(' ');
        }
        String s = sb.toString();

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(field[k][0]));
        bw.newLine();
        bw.write(s);
        bw.flush();
        bw.close();
    }

    private static void push(int[][] field) {
        int iter = k;
        while (iter != n) {
            stack.push(iter);
            iter = field[iter][1];
        }
        stack.push(n);
    }

    private static void bfs(int[][] field) {

        Queue<Integer> que = new LinkedList<>();
        field[n][0] = 0;
        que.add(n);
        while (!que.isEmpty()) {
            int num = que.poll();
            for (int i = 0; i < 3; i++) {

                int nx = (i == 0) ? num * 2 : num + dx[i];
                if (nx < 0 || nx > 100000) continue;
                if (field[nx][0] != -1) continue;

                field[nx][1] = num;
                field[nx][0] = field[num][0] + 1;

                if (nx == k) {
                    return;
                }
                if(nx!=0) que.add(nx);
            }
        }
    }
}

나는 field를 2차원 배열로 선언해서

field[idx][0]에는 전에 방문했던 번호
field[idx][1]에는 몇번째 방문인지 카운팅을 했다.

배열을 애초에 두개로 나누어도 괜찮았을 듯.