BOJ - 숨바꼭질 (1697)

https://www.acmicpc.net/submit/1697/31937024

로그인

 

• 그래프 탐색 문제이나 BFS와 DFS가 섞인 문제이다.
• BFS로 최단 경로를 찾고 DFS로 최단 경로까지 이동을 찾는 문제이다.

 

import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws Exception {

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        boolean[] visited = new boolean[100000 + 1];

        ArrayList<Integer>[] adj = new ArrayList[100000 + 1];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayList<>();
        }

        ArrayList<State> visitedNodes = new ArrayList<>();
        Queue<State> queue = new LinkedList<>();
        queue.add(new State(N, 1));

        int goldDepth = 1;
        while (!queue.isEmpty()) {
            State node = queue.poll();
            if (node.currentNode < 0 || node.currentNode > 100000) continue;
            if (visited[node.currentNode] == true) continue;
            visited[node.currentNode] = true;
            visitedNodes.add(node);

            if (node.currentNode == K) {
                goldDepth = node.depth;
                break;
            }

            queue.add(new State(node.currentNode - 1, node.depth + 1));
            adj[node.currentNode].add(node.currentNode - 1);
            queue.add(new State(node.currentNode + 1, node.depth + 1));
            adj[node.currentNode].add(node.currentNode + 1);
            queue.add(new State(node.currentNode * 2, node.depth + 1));
            adj[node.currentNode].add(node.currentNode * 2);
        }

        System.out.println(goldDepth - 1);
    }

    private static void dfs(ArrayList<Integer> path, Integer currentNode, boolean[] visited, ArrayList<Integer>[] adj, int depth, int golaDepth, int goal) {
        if (currentNode >= adj.length) return;
        if (visited[currentNode] == true) return;
        if (depth > golaDepth) return;

        visited[currentNode] = true;
        path.add(currentNode);

        if (currentNode == goal) {
            for (int i = 0; i < path.size(); i++) {
                System.out.print(path.get(i) + " ");
            }
            System.exit(0);
            return;
        }

        for (int i = 0; i < adj[currentNode].size(); i++) {
            Integer next = adj[currentNode].get(i);
            dfs(path, next, visited, adj, depth + 1, golaDepth, goal);
        }
        visited[currentNode] = false;
        path.remove(currentNode);
    }
}

class State {
    public int currentNode;
    public int depth;

    public State(int currentNode, int depth) {
        this.currentNode = currentNode;
        this.depth = depth;
    }
}