[백준] DFS 스페셜 저지 (16964번)

1. 문제 해석

사용자가 DFS를 통해 정답을 제출했을 때 복수의 정답을 채점하는 경우의 알고리즘을 짜는 문제이다

즉 답이 여러 개일 경우 해당 제출한 답이 맞는지 확인하는 코드를 작성하는 문제이다

 

2. 사용되는 자료구조

• Set<Integer>[] 인접 리스트 사용
  
  • 목적 : 노드끼리 연결된 노드들만 저장하기 위해 사용
  • 이유 : 
    • 인접 행렬(int[][])를 사용했을 때 공간 복잡도에 걸림
    • 또한 List<Integer>[]를 사용했을 때 해당 노드에 접근하는데 시간복잡도(73%에서 걸렸습니다)가 걸림
• Stack<Integer>
  • 목적 : 사용자가 입력한 값을 이용하여 해당 노드로 접근이 가능한지 파악할 때 접근을 할 수 없다면 이전 노드로 돌아가야 하기 때문
  • 이유 : 매개변수로 제어해볼려고 했었지만 이전의 이전 노드를 저장할 수 없어 사용하게 되었음

 

3. 핵심 아이디어

• 최초에는 DFS로 나올 수 있는 값을 전부 출력해볼려고 했지만 사용자가 입력한 값이 올바른지만 확인하면 되는 문제였음
• 예시 ) 1, 2, 4, 3의 값이 들어왔을 때(백준 예제)
  • 1이 2와 연결되었는지(연결 O)
  • 2는 4랑 연결되었는지(연결 O)
  • 4는 3이랑 연결되었는지(연결 X)
  • 2는 3이랑 연결되었는지(연결 X)
  • 1는 3이랑 연결되었는지 (연결 O)
• 현재 노드와 탐색할려는 사용자의 입력 값의 idx를 잘 관리하면 되는 문제

 

---

정답은 더보기 클릭

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static Set<Integer>[] graph;

    static boolean flag = false;

    static int[] input;

    static int N;
    static Stack<Integer> stk = new Stack<>();

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        input = new int[N];
        graph = new Set[N+1];
        for (int i = 0; i <= N; i++) {
            graph[i] = new HashSet<>();
        }

        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        
        // 시작 노드가 1이 아니라면 0을 출력하고 종료
        // 이것을 하지 않았을 때 99%에서 틀림
        if (input[0] != 1) {
            System.out.println(0);
            return;
        }

        dfs(0, 1);

        System.out.println(flag ? 1 : 0);
    }

    public static void dfs(int curIdx, int targetIdx) {
        // 사용자 입력 idx가 끝까지 간 경우 true, 명령어 종료
        if (targetIdx == N) flag = true;
        if (flag) return;

        // 그래프가 연결되어 있는지
        // List<Integer>[] 로 하였을 시 contains 메소드는 n이라는 시간 복잡도가 걸리기 때문에 Set<Integer>[] 사용
        if (graph[input[curIdx]].contains(input[targetIdx])) {
            // 이전 노드를 저장하기 위해 사용(이전의 이전의 이전의 노드 등등 전부 저장하고 있어야함)
            stk.push(curIdx);
            
            // 연결한 노드와 다음 노드를 인자로 가지고 감
            dfs(targetIdx, targetIdx+1);
        } else {
            // 연결되지 않았을 때
            // 만약 이전 노드가 존재하지 않는다면 종료
            if (stk.isEmpty()) return;

            // 이전 노드를 가지고 현재 idx를 비교해야함
            dfs(stk.pop(), targetIdx);
        }
    }
}