백준_1697_숨바꼭질

숨바꼭질

풀이

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

public class Main {
	static int N,K,ans;
	static int[] map;
 	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[100_001];

		dfs(N);
	}
	static void dfs(int n) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(n);
		
		map[n] = 1;
		
		while(!q.isEmpty()){
			int now = q.poll();
			
			if (now == K) {
				System.out.println(map[now] - 1); // 맨처음 시작
			}
			if (now - 1 >= 0 && map[now - 1] == 0) {
				map[now - 1] = map[now] + 1;
				q.add(now - 1);
			}
			if (now + 1 <= 100000 && map[now + 1] == 0) {
				map[now + 1] = map[now] + 1;
				q.add(now + 1);
			}
			if (2 * now <= 100000 && map[2 * now] == 0) {
				map[2 * now] = map[now] + 1;
				q.add(2 * now);
			}
			
		}
	}

}

BFS는 레벨별로 탐색을 진행하기 때문에 최단 경로 문제에 적합하다~!

map[n] = 1;
...
System.out.println(map[now] - 1);

• 시작점이 같을때도 한번에 처리 가능!

처음엔 dfs로 풀었는데 "시간초과" 발생!

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

public class Main2 {
    static int N, K, ans;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new boolean[100_001];
        ans = Integer.MAX_VALUE;

        dfs(N, 0);
        System.out.println(ans);
    }

    static void dfs(int n, int cnt) {
        if (n < 0 || n > 100000 || visited[n]) {
            return;
        }

        if (n == K) {
            ans = Math.min(ans, cnt);
            return;
        }

        visited[n] = true;

        dfs(n - 1, cnt + 1);
        dfs(n + 1, cnt + 1);
        dfs(2 * n, cnt + 1);

        visited[n] = false;
    }
}

위풀이는 너무 많은 재귀를 하게 됨!