[백준 4803] 트리 - Java 문제풀이

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

 

출력

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

 

접근

1. 트리 = 사이클이 있지 않은 그래프이기 때문에 사이클이 있는지 확인해보며, 사이클이 없는 연결요소라면 트리라고 판단해준다.
2. parent[i]가 이미 i가 아니라면(자신이 루트가 아니라면) 이미 다른 연결요소에 포함된 것이기 때문에 다음 노드로 넘겨준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, M;
    private static int[][] arr, result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        result = new int[N][M];
        for(int i=0;i<N;i++) Arrays.fill(result[i], -1);
        result[0][0] = 1;
        System.out.println(recur(N-1, M-1));
    }
    private static int[] dx = new int[]{-1, 1, 0, 0};
    private static int[] dy = new int[]{0, 0 , -1, 1};
    private static int recur(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= M) return 0;
        else if (result[x][y] != -1) return result[x][y];

        result[x][y] = 0;

        for(int k=0;k<4;k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (arr[x][y] < arr[nx][ny]) result[x][y] += recur(nx, ny);
        }
        return result[x][y];
    }
}