[백준/Java] 4803번 : 트리

🌵 문제 분석

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

1. 노드 N개가 1개 이상의 간선으로 연결되어있고

2. 임의의 두 정점에 대해서는 경로가 유일하다고 할 때

모든 정점이 서로 연결되어 있는 그래프를 '연결 요소'라고 한다.

 

사이클이 없는 연결 요소의 개수가 T일 때

T==0일 때 No trees.

T==1일 때 There is one tree.

T>1일 때 A forest of T trees.

를 출력하라.

 

입력 : 

N(노드 개수) M(간선 개수)

M개의 간선

N==0, M==0일 때까지 위 입력을 받음

🌵 구현 아이디어

1. 이중 연결리스트에 양방향으로 간선 정보를 저장한다.
2. 아직 방문하지 않은 모든 노드에 대하여 DFS 탐색을 한다.
3. DFS 탐색 결과 사이클이 아니면 트리 하나로 센다.
4. 모든 노드 방문이 끝났으면 트리 개수에 따라 문장을 출력한다.

🤔 사이클인지 확인하는 방법

dfs 탐색 도중에 다음으로 탐색할 인접 노드가

이미 방문한 노드이면서 본인의 부모 노드가 아니면 사이클이다.

 

예)

  1
 /  \
2   3
 \  /
  4

 

이 형태의 그래프에서 dfs 탐색하면 1->2->4->3까지 탐색 후

3에서 다시 1을 방문하려 할 텐데 1은 이미 방문했으며 3의 부모 노드가 아니다. 

따라서 사이클이라고 판단할 수 있다.

🌵 시간 복잡도

모든 노드를 DFS로 한 번만 탐색하므로 O(N)

N은 최대 500이므로 1초 내에 탐색 가능

🌵 알고리즘

그래프 탐색

🌵 코드 설계

1. 입력 받기
   1. 무한 루프를 돌다가 N, M이 0, 0이면 탈출
   2. 간선 정보 M개 이중 연결 리스트에 저장
2. 모든 노드에 대해 dfs 탐색하면서 사이클인지 확인하기
   1. 현재 노드 방문체크 해주고
   2. 현재 노드와 인접한 노드를 하나씩 방문하면서
      이미 방문한 곳 && 현재 노드의 부모노드인지 확인
   3. 맞다면 cycle=true
   4. 아니라면 계속 dfs 탐색
3. dfs 탐색 결과 사이클일 때만 treeCnt++
4. treeCnt 개수에 따라 문장 출력하기

🌵 정답 코드

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

public class Main {
    static List<List<Integer>> list;
    static boolean[] visited;
    static boolean cycle;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        boolean isEnd = false;
        int caseNum = 1;

        while(true){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            if(N==0 && M==0) return;

            //인접 리스트 생성
            list = new ArrayList<>();
            for(int i=0; i<N+1; i++){
                list.add(new ArrayList<>());
            }
            for(int i=0; i<M; i++){
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());
                list.get(node1).add(node2);
                list.get(node2).add(node1);
            }

            //방문체크 배열 생성
            visited = new boolean[N+1];

            //트리의 개수 저장하는 변수
            int treeCnt = 0;

            //모든 노드에 대해서 DFS
            for(int i=1; i<=N; i++){
                //아직 방문하지 않은 노드면 dfs탐색
                if(!visited[i]){
                    cycle = false;
                    dfs(i, -1);
                    //dfs 결과 사이클이 아니었다면 트리 하나 세기
                    if(!cycle) treeCnt++;
                }
            }

            StringBuilder sb = new StringBuilder();
            sb.append("Case " + caseNum + ": ");
            caseNum++;

            if(treeCnt==0){
                sb.append("No trees.");
            }else if(treeCnt==1){
                sb.append("There is one tree.");
            }else if(treeCnt>1){
                sb.append("A forest of " + treeCnt + " trees.");
            }
            System.out.println(sb);
        }
    }

    static void dfs(int now, int parent) {
        visited[now] = true;

        //now와 인접한 노드 방문
        for (int next : list.get(now)) {
            //아직 방문하지 않았다면 dfs탐색
            if (!visited[next]) {
                dfs(next, now);
            } else if (next != parent) {
                // 방문한 적이 있는데 부모 노드가 아니라면 사이클 발생
                cycle = true;
            }
        }
    }
}