반응형
05-15 00:00
Today
Total
«   2024/05   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
관리 메뉴

개발하는 고라니

[백준] 4803번 : 트리 본문

Programming/백준

[백준] 4803번 : 트리

조용한고라니 2021. 5. 26. 02:07
반응형
 

4803번: 트리

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

www.acmicpc.net


[DFS]

다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다.

 

사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다.

    static boolean DFS(int x, int before){
        if(visit[x])
            return false;

        boolean result = true;
        visit[x] = true;

        for(int next:list[x])
            if(next != before)
                result &= DFS(next, x);

        return result;
    }

위 코드는 DFS 메서드인데, boolean 타입을 반환한다. 반환 값이 true이면 트리라는 뜻이고, false면 사이클이 존재하므로 그래프가 된다.

 

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List<Integer>[] list;
    static boolean[] visit;

    static boolean DFS(int x, int before){
        if(visit[x])
            return false;

        boolean result = true;
        visit[x] = true;

        for(int next:list[x])
            if(next != before)
                result &= DFS(next, x);

        return result;
    }

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

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            if(n == 0 && m == 0) break;

            list = new ArrayList[n+1];
            visit = new boolean[n+1];

            for(int i=1; i<=n; i++){
                list[i] = new ArrayList<>();
            }

            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());

                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                list[v1].add(v2);
                list[v2].add(v1);
            }

            int cnt = 0;
            for(int i=1; i<=n; i++)
                if(!visit[i] && DFS(i, 0))
                    cnt++;

            sb.append(String.format("Case %d: ", t++));

            if(cnt == 0)      sb.append("No trees.");
            else if(cnt == 1) sb.append("There is one tree.");
            else              sb.append(String.format("A forest of %d trees.", cnt));

            sb.append('\n');
        }
        System.out.print(sb);
    }
}
반응형

'Programming > 백준' 카테고리의 다른 글

[백준] 1181번 : 단어 정렬  (0) 2022.02.01
[백준] 12763번 : 지각하면 안 돼  (0) 2021.05.30
[백준] 18405번 : 경쟁적 전염  (0) 2021.05.26
[백준] 3709번 : 레이저빔은 어디로  (0) 2021.05.13
[백준] 5430번 : AC  (0) 2021.05.12
Comments