워료일.....😇

문제링크

백준 #4803. 트리

풀이방법

정점과 간선 정보가 주어지면 몇개의 트리를 가지고 있는지 판단하는 문제이다.

트리의 조건은 다음과 같다.

• 정점이 n개 일때, 간선은 n - 1개 이다
• 사이클이 없다
• 두 정점 사이에 유일한 경로를 갖는다

여기서 2, 3번째는 같은 의미를 내포하고 있다고 생각하고, 사이클 여부는 첫번째 조건으로 판단 가능하다고 생각했다. 사이클이 생기려면 간선의 개수가 적어도 n개가 되어야하기 때문!

다른 그래프 문제들은 거의 정점 방문여부만 판단하면 됐었는데 해당 문제에서는 다른 경로로 해당 정점을 재방문하는지도 알아야해서 인접리스트가 아닌 인접행렬을 이용해 구현했다(이런 경우 구현이 더 간편하다고 생각했음). 인접행렬에 isPath, isWent 변수를 넣어 정점에 대한 방문 여부를 체크하지 않고 간선에 대한 사용 여부를 체크했다(간선에 isWent = true로 설정하는데, 배열 사용 시 원타임에 접근할 수 있기 때문에 인접행렬 사용). 간선과 정점 방문 시 각각을 카운트하고, 마지막에 (nodes == edge + 1)을 따져 하나의 트리인지를 확인했다 ! ! !

코드

import java.util.Scanner;

public class Tree {
    static boolean[] visited = new boolean[501];
    static Area[][] graph = new Area[501][501];

    static int nodes = 0;
    static int edges = 0;

    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder result = new StringBuilder();

        n = sc.nextInt();
        int m = sc.nextInt();

        for (int i = 1; i <= 500; i++) {
            for (int j = 1; j <= 500; j++) graph[i][j] = new Area();
            visited[i] = false;
        }

        int count = 0;
        int caseCount = 1;
        while ((n != 0) || (m != 0)) {
            for (int i = 0; i < m; i++) {
                int parentNode = sc.nextInt();
                int childNode = sc.nextInt();

                graph[parentNode][childNode].isPath = true;
                graph[childNode][parentNode].isPath = true;
            }

            for (int i = 1; i <= n; i++) {
                nodes = 0;
                edges = 0;
                if (!visited[i]) {
                    searchTree(i);
                    if (nodes == edges + 1) count++; // 트리의 조건을 이용해 트리여부 판단
                }
            }

            result.append("Case " + caseCount + ": ");
            if (count == 0) result.append("No trees.\n");
            else if (count == 1) result.append("There is one tree.\n");
            else result.append("A forest of " + count + " trees.\n");

            resetGlobalVars();
            count = 0;
            caseCount++;

            n = sc.nextInt();
            m = sc.nextInt();
        }

        System.out.print(result.toString());
    }

    static void resetGlobalVars() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) graph[i][j].initVars();
            visited[i] = false;
        }
    }

    static void searchTree(int node) {
        if (!visited[node]) {
            visited[node] = true;
            nodes++;
        }

        for (int i = 1; i <= n; i++) {
            if (graph[node][i].isPath && !graph[node][i].isWent) {
                edges++;
                graph[node][i].isWent = true;
                graph[i][node].isWent = true;

                searchTree(i);
            }
        }
    }
}

class Area {
    public boolean isPath;
    public boolean isWent;

    public Area() {
        isPath = false;
        isWent = false;
    }

    public void initVars() {
        isPath = false;
        isWent = false;
    }
}

🙇🏻‍♀️🙇🏻‍♀️

주말돌려조..