[백준] 11266번 단절점 (JAVA)

문제

https://www.acmicpc.net/problem/11266

11266번: 단절점

 

설명

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다.

각 정점들마다 방문 순서를 부여하기 위한 visited[] 배열과 단절점인지 판단하기 위한 isCutPoint[] 배열을 선언하고 정점간의 연결관계를 입력받아 인접리스트를 만들어준다.

방문하지 않은 정점을 시작으로 DFS 탐색을 수행하여 order를 저장하고 단절점을 찾는다.

 

cutPountSearch 함수에서는 각 정점의 order를 통해 단절점인지 판단한다.

order는 초기값으로 자기 자신의 방문 순서를 가진다.

현재 정점이 루트 노드가 아닌 경우에는 자기 자신과 인접한 정점들의 order 중 가장 작은 order 값이 자기 자신의 order보다 크거나 같다면 해당 정점은 단절점으로 판단한다.

현재 정점이 루트 노드이면서 자식 노드가 2개 이상인 경우에는 해당 정점은 단절점으로 판단한다.

int cutPointSearch(int curNode, int root) {
    // 루트 노드일 때 자식 노드가 몇 개인지 파악
    int childNodeCnt = 0;

    // 방문 순서
    visited[curNode] = visitOrder++;

    // 방문한 점의 인접한 minOrder
    // 초기화는 자기 자신의 순서
    int minOrder = visited[curNode];

    // current Node와 인접한 인접리스트 탐색 진행
    for (int i = 0; i < adjList.get(curNode).size(); i++) {
        int destNode = adjList.get(curNode).get(i);

        // 만일 방문을 한 곳이라면
        if (visited[destNode] != 0) {
            minOrder = Math.min(minOrder, visited[destNode]);
            continue;
        }

        // 자식 Order는 DFS를 한 번 더 돌린다.
        int childOrder = cutPointSearch(destNode, 1);

        // 루트노드가 아닌 경우
        // 자기 자신의 order와 자기 자신과 인접한 정점들의 order 중 가장 작은 order
        if (root == 1 && childOrder >= visited[curNode]) {
            if (!isCutPoint[curNode])
                cutPointCnt++;
            isCutPoint[curNode] = true;
        }

        minOrder = Math.min(minOrder, childOrder);
        childNodeCnt++;
    }

    if (root == 0 && childNodeCnt > 1) {
        if (!isCutPoint[curNode])
            cutPointCnt++;
        isCutPoint[curNode] = true;
    }

    return minOrder;
}

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int V, E;
    static ArrayList<ArrayList<Integer>> adjList;
    static int[] visited;
    static int visitOrder;
    static boolean[] isCutPoint;
    static int cutPointCnt;

    // DFS 수행부
    static int cutPointSearch(int curNode, int root) {
        // 루트 노드일 때 자식 노드가 몇 개인지 파악
        int childNodeCnt = 0;

        // 방문 순서
        visited[curNode] = visitOrder++;

        // 방문한 점의 인접한 minOrder
        // 초기화는 자기 자신의 순서
        int minOrder = visited[curNode];

        // current Node와 인접한 인접리스트 탐색 진행
        for (int i = 0; i < adjList.get(curNode).size(); i++) {
            int destNode = adjList.get(curNode).get(i);

            // 만일 방문을 한 곳이라면
            if (visited[destNode] != 0) {
                minOrder = Math.min(minOrder, visited[destNode]);
                continue;
            }

            // 자식 Order는 DFS를 한 번 더 돌린다.
            int childOrder = cutPointSearch(destNode, 1);

            // 루트노드가 아닌 경우
            // 자기 자신의 order와 자기 자신과 인접한 정점들의 order 중 가장 작은 order
            if (root == 1 && childOrder >= visited[curNode]) {
                if (!isCutPoint[curNode])
                    cutPointCnt++;
                isCutPoint[curNode] = true;
            }

            minOrder = Math.min(minOrder, childOrder);
            childNodeCnt++;
        }

        if (root == 0 && childNodeCnt > 1) {
            if (!isCutPoint[curNode])
                cutPointCnt++;
            isCutPoint[curNode] = true;
        }

        return minOrder;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        // 방문 순서 체크
        visited = new int[V + 1];
        // 단절점인지 체크
        isCutPoint = new boolean[V + 1];

        adjList = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            adjList.add(new ArrayList<>());
        }

        // a와 b를 입력받아서 인접리스트를 만들어준다
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            adjList.get(A).add(B);
            adjList.get(B).add(A);
        }

        visitOrder = 1;

        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0)
                cutPointSearch(i, 0);
        }

        System.out.println(cutPointCnt);
        for (int i = 1; i <= V; i++) {
            if (isCutPoint[i])
                System.out.print(i + " ");
        }
    }
}