백준 4803 트리 Java

solved.ac = 골드 4

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

4803번: 트리

 

1. 접근

 

문제를 풀기 전 시간 복잡도를 구하자!

V + E를 T만큼 반복하는데 T는 제시되어 있지 않다!

n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자!

 

문제의 조건을 살펴보면

트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 

이 형식에 맞춰서 출력해주면 된다.

 

조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n - 1을 충족하며 순환되지 않는 그래프이다.

즉, 간선의 수 == (간선 개수 - 1) * 2 (무방향 그래프로 양쪽 간선은 서로 연결되어 있으니 * 2로 확인한다)

 

예제의 첫 번째 케이스를 그림으로 살펴보면 (N = 6, M = 3)

여기서 주의할 점은 5번 노드나 6번 노드처럼 연결되어 있는 간선이 없더라도 5 -> 5, 6 -> 6도 카운트해야 한다.

매 케이스마다 위 그림처럼 트리의 개수를 세어 출력하자!

 

2. 풀이

 

변수 세팅

static int N, M, vertexCnt, edgeCnt, caseCnt;
static ArrayList<Integer>[] graph;
static boolean[] visit;
public static void main(String[] args) throws IOException {
    caseCnt = 0;
    while (true) {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if (N == 0 && M == 0) break; // 입력의 마지막은 0, 0
        visit = new boolean[N + 1];
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            graph[y].add(x);
        }
        solution();
    }
    System.out.println(sb.toString());
}

 

DFS 호출 및 정답 출력

static void solution() {
    caseCnt++;
    int treeCnt = 0;
    for (int i = 1; i <= N; i++) {
        if (visit[i]) continue; // 방문여부 확인!
        vertexCnt = 0;
        edgeCnt = 0;
        DFS(i);
        // 트리의 조건 = 간선(edge)는 정점(vertex)의 갯수 - 1개 있어야 한다.
        // 무방향 그래프로 *2 하여 비교한다.
        if (edgeCnt == (vertexCnt - 1) * 2) treeCnt++;
    }
    sb.append("Case ").append(caseCnt).append(": ");
    if (treeCnt == 0) sb.append("No trees.");
    else if (treeCnt == 1) sb.append("There is one tree.");
    else sb.append("A forest of ").append(treeCnt).append(" trees.");
    sb.append('\n');
}

 

DFS

static void DFS(int x) {
    vertexCnt++; // 정점 갯수 카운트!
    edgeCnt += graph[x].size(); // graph[x].size == 해당 정점에 연결 된 간선의 수
    visit[x] = true; // 방문처리!
    for (int y : graph[x]) {
        if (visit[y]) continue; // 방문여부 확인!
        DFS(y);
    }
}

 

3. 전체 코드