알고리즘 풀이 - 백준 16964(DFS 스페셜 저지, 그래프(DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

주어진 순서가 DFS로 풀 수 있는 것인지 확인하는 문제

 

 

2. 풀이

 

이전 포스팅(여기) 에서 주어진 순서가 BFS로 탐색이 가능한지를 풀어보는 문제를 진행했었다. 

BFS에서는 2가지의 방법으로 풀었지만 여기서는 그 2가지 중 ②번 방법만 사용한다.

DFS는 특성상 ①의 방법을 사용하기가 어렵다.(사실 가능한지조차 모르겠다.) 따라서 ②번 방법을 쓴다.

 

②번 방법은 현재 주어진 값을 기반으로 그래프를 정렬한 뒤 단순히 DFS 탐색을 수행하는 방법이다.

그래프 탐색은 기본적으로 현재 정점에 연결된 정점의 순서를 어떻게 정하느냐에 따라 그 결과가 달라질 수밖에 없다. 따라서 주어진 순서에 기반하여 정렬한 뒤 DFS를 수행하고 그 결과가 일치하지 않으면 불가능한 경우라고 판정할 수 있다.

이를 이용한 코드는 아래를 참조

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static ArrayList<Integer>[] graph;
    static int[] num;
    static int[] order;   // 주어진 순서 값을 저장하는 배열
    static boolean[] visited; // 각 정점의 방문 완료 여부 저장 배열
    static ArrayList<Integer> dfs_result = new ArrayList<>(); // dfs 탐색 결과 저장
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // ************** 그래프 초기화 ******************
        graph = new ArrayList[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        StringTokenizer st = null;
        for(int i=1; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            graph[u].add(v);
            graph[v].add(u);
        }
        // ************* 여기까지 그래프 생성 완료 ****************
        
        
        // ************* 주어진 탐색 순서를 저장 *********************
        num = new int[n+1];
        order = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i <= n; i++){
            num[i] = Integer.parseInt(st.nextToken());
            order[num[i]] = i;
        }
        // ************* 주어진 탐색 순서 저장 완료 ******************
        
        // ************* 저장된 순서값을 기반으로 Graph 내 정점을 정렬 *************
        for(int i=1; i <= n; i++){
            Collections.sort(graph[i], new Comparator<Integer>(){
                public int compare(Integer u, Integer v){
                    if(order[u] < order[v]){
                        return -1;
                    } else if(order[u] == order[v]){
                        return 0;
                    } else {
                        return 1;
                    }
                }
            });
        }
        // ************* 순서값 기반 Graph 정점 정렬 완료 ************************
        
        
        // ************* 정렬된 순서 기반 DFS 탐색 수행 후 결과값 표시 ************
        visited = new boolean[n+1];
        dfs(1);
        boolean ans = true;
        for(int i=1; i <= n; i++){
            if(dfs_result.get(i-1) != num[i]){
                ans = false;
            }
        }
        
        if(ans){
            System.out.println(1);
        } else {
            System.out.println(0);
        }
        br.close();
        // ****************************** 완료 *********************************
    }
    
    // DFS 를 수행하는 메소드
    private static void dfs(int x){
        if(visited[x]) return;
        dfs_result.add(x);
        visited[x] = true;
        
        for(int y : graph[x]){
            dfs(y);
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.