BOJ_1697 숨박꼭질 [Java] (S1)

문제 설명

풀이

기본적인 BFS 문제, 이런 경우 DFS로 할경우 오히려 늦어지는 경우가 많았음. BFS로 모든 경우의 수를 찾아가면 금방 찾아감!

 

코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[100001];
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        visit[N] = 1;

        while (!que.isEmpty()) {
            int out = que.poll();

            if (out == M) {
                return visit[out]-1;
            }
            if ( out * 2 <= 100000 && visit[out * 2] == 0){
                visit[out*2] = visit[out] + 1;
                que.add(out * 2);
            }
            if ( out + 1 <= 100000 && visit[out + 1] == 0 ){
                visit[out+1] = visit[out] + 1;
                que.add(out + 1);
            }
            if ( out - 1 >= 0 && visit[out -1] == 0 ){
                visit[out-1] = visit[out] + 1;
                que.add(out - 1);
            }
        }

        return -1;
    }
}

 

왜 틀린건지 모르는 내 해쉬를 사용한 코드...

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static long N,M;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        M = Long.parseLong(st.nextToken());
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();
            System.out.println(out[0]+"count : "+ out[1]);

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] + 1 <= M && !map.containsKey(out[0] + 1) ){
                map.put(out[0] + 1, out[1]+1);
                que.add(new long[] {out[0] + 1,out[1]+1});
            }
            if ( out[0] - 1 > 0 && !map.containsKey(out[0] - 1) ){
                map.put(out[0] - 1, out[1]+1);
                que.add(new long[] {out[0] - 1,out[1]+1});
            }
        }

        return -1;
    }
}

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질