[백준] 33888번 : 가오리 그래프[Java]

 

#풀이

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



public class Main {
    static int N;
    static ArrayList<Integer>[] graph;
    static int[] abcdef = new int[6]; // A B C D E F
    static boolean[] visited;

    static void dfs(int now) {
        // E찾기
        if(abcdef[4]==0&&graph[now].size()==4){
            abcdef[4] = now;
        }
        // C찾기
        if(abcdef[4]!=now&&graph[now].size()==4){
            abcdef[2] = now;
            return ;
        }
        visited[now] = true;
        // B A D 찾기 (간선 3개인 노드)
        if (graph[now].size() == 3) {
            if(abcdef[1]==0) abcdef[1] = now;
            else if(abcdef[0]==0)abcdef[0] = now;
            else if(abcdef[3]==0)abcdef[3] = now;

        }


        for (int next : graph[now]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+1];
        visited = new boolean[N+1];
        for(int i =0; i<N+1; i++){
            graph[i] = new ArrayList<>();
        }

        int U,V;
        for(int i = 0; i<N+3; i++){
            st = new StringTokenizer(br.readLine());
            U = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());
            graph[U].add(V);
            graph[V].add(U);
        }
        
        for(int i = 0; i<graph.length; i++){
            if(graph[i].size()==1){
                dfs(i);
                abcdef[5] = i;
            }
        }
        // swap
        if(abcdef[1]>abcdef[3]){ //D>B조건 만족
            int temp = abcdef[3];
            abcdef[3] = abcdef[1];
            abcdef[1] = temp;
        }
        for(int k:abcdef)System.out.print(k+" ");


    }
}

#성능

#정리

간선이 2개인 정점은 핵심 정점이 아니다.

탐색은 DFS로 수행한다.

1. 간선이 1개인 노드(꼬리 F)를 찾는다.

2. 꼬리부터 DFS를 타고, 간선이 4개인 노드를 만날 때까지 탐색한다. 이 노드를 발견하면 핵심 정점 E로 할당한다.

3. 이후 DFS로 끝까지 탐색한다.

3-1. 탐색 중 또 다른 간선 4개인 노드가 나온다면, 해당 노드를 핵심 정점 C로 할당한다.

3-2. 탐색 중 간선이 3개인 노드를 발견할 때마다 순서대로 핵심 정점 B, A, D에 값을 할당한다.

4. 마지막으로 D > B 조건을 만족하도록 순서를 조정한다.