[BOJ 4803, Java] 트리

문제 링크

BOJ 4803

분류

자료 구조(data_structures), 깊이 우선 탐색(dfs), 분리 집합(disjoint_set), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 트리(trees)

설명

트리의 성질을 통해 트리의 갯수를 카운팅하는 문제였다. 이 문제에서는 연결 요소로 구성된 것들 중에 사이클을 배제하는 것으로 해결할 수 있다.

1. 모든 노드에 대해 방문 확인
2. 방문하지 않은 점에 대해서 트리에 편입하면서 깊이 탐색
3. 사이클을 형성한 경우 구성하고 있는 모든 점을 방문 처리
4. 사이클을 형성하지 않았다면 해당 집합은 트리이므로 1 카운트

위와 같은 로직을 통해 구현하였고 깊이탐색을 하면서 카운팅 처리를 어떻게 할까 고심한 결과 아래와 같은 코드를 구성하였다.

    public static int dfs(int nowNode, int parent, boolean[] visitLog, HashMap<Integer, ArrayList<Integer>> graph) {

        for (int nextNode : graph.get(nowNode)) {

            if (nextNode != parent && !visitLog[nextNode]) {

                visitLog[nextNode] = true;

                int result = dfs(nextNode, nowNode, visitLog, graph);
                if (result == 0) {
                    return 0;
                }

            } else if (nextNode != parent && visitLog[nextNode]) {
                return 0;
            }

        }

        return 1;

    }

최초 지점에서부터 재귀의 형태로 방문 처리하며 조사를 하다가 사이클이 나온 경우 기본적으로 모든 지점을 순회한 다음 0을 반환하는 구조로 작성했다.

만약 사이클이 나타나지 않았다면 정상적으로 순회를 마무리하고 1을 반환하여 해당 함수의 반환값을 계속 카운팅하면 트리의 갯수를 확인할 수 있다!

풀이 코드

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

public class Main {

    public static int dfs(int nowNode, int parent, boolean[] visitLog, HashMap<Integer, ArrayList<Integer>> graph) {

        for (int nextNode : graph.get(nowNode)) {

            if (nextNode != parent && !visitLog[nextNode]) {

                visitLog[nextNode] = true;

                int result = dfs(nextNode, nowNode, visitLog, graph);
                if (result == 0) {
                    return 0;
                }

            } else if (nextNode != parent && visitLog[nextNode]) {
                return 0;
            }

        }

        return 1;

    }

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

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = 0;

        ArrayList<String> outputArr = new ArrayList<>();

        while (true) {

            StringTokenizer treeInfo = new StringTokenizer(input.readLine(), "[ ]");
            int nodeNumber = Integer.parseInt(treeInfo.nextToken());
            int edgeNumber = Integer.parseInt(treeInfo.nextToken());

            if (nodeNumber == 0 && edgeNumber == 0) {
                break;
            }

            testCase += 1;

            int treeCount = 0;
            boolean[] isVisited = new boolean[nodeNumber + 1];

            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("Case ");
            stringBuilder.append(testCase);
            stringBuilder.append(": ");

            HashMap<Integer, ArrayList<Integer>> treeGraph = new HashMap<>();
            for (int i = 1; i < nodeNumber + 1; i++) {
                treeGraph.put(i, new ArrayList<>());
            }

            for (int i = 0; i < edgeNumber; i++) {

                StringTokenizer edgeInfo = new StringTokenizer(input.readLine(), "[ ]");
                int startNode = Integer.parseInt(edgeInfo.nextToken());
                int endNode = Integer.parseInt(edgeInfo.nextToken());

                treeGraph.get(startNode).add(endNode);
                treeGraph.get(endNode).add(startNode);

            }

            for (int i = 1; i < nodeNumber + 1; i++) {

                isVisited[i] = true;
                treeCount += dfs(i, 0, isVisited, treeGraph);
            }

            if (treeCount == 0) {
                stringBuilder.append("No trees.");
            } else if (treeCount == 1) {
                stringBuilder.append("There is one tree.");
            } else if (treeCount > 1) {
                stringBuilder.append("A forest of ");
                stringBuilder.append(treeCount);
                stringBuilder.append(" trees.");
            }

            outputArr.add(stringBuilder.toString());

        }

        for (int i = 0; i < testCase; i++) {

            if (i != testCase - 1) {
                output.write(outputArr.get(i) + "\n");
            } else {
                output.write(outputArr.get(i));
            }

        }

        output.flush();
        output.close();

    }

}