[BOJ] 4803 트리 - JAVA

1. 문제

4803번: 트리

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

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

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

---

2. 풀이

메인

1.  부모를 저장하는 set, 해당 부모가 tree가 맞는지 저장하는 root 배열을 사용한다. set은 자기 자신으로 초기값을 넣고 root는 true를 저장한다. (19~22)

2.  간선을 입력받으면서 union 시킨다. 

3.  모두 입력받은 뒤에 root의 개수를 센다.(true 개수)

4.  형식에 맞게 출력한다.

static int N, M;
static int[] set;
static boolean[] root;

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

   while (!(line = in.readLine()).equals("0 0")) {
      st = new StringTokenizer(line);
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      set = new int[N + 1];
      root = new boolean[N+1];

      for(int i=1;i<=N;i++) {
         set[i] = i;
         root[i] = true;
      }

      for(int m=0;m<M;m++){
         st = new StringTokenizer(in.readLine());
         union(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
      }

      int count = 0;
      for(int i=1;i<=N;i++) if(root[i]) count++;

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

   System.out.print(sb);
}

 

Find

저장된 값과 인덱스가 같다면 그 x가 루트다. 바로 반환한다.

아니라면 저장된 값을 find(set[x])로 변경한다.

private static int find(int x){
   if(set[x]==x) return x;
   return set[x] = find(set[x]);
}

 

Union

1.  부모루트를 찾는다. 부모루트가 같고 간선의 양 끝점이 다르다면 싸이클이 일어난 것이므로 root에 false를 저장한다.

2.  부모루트가 같고 간선의 양 끝점이 같다면 자기자신이므로 아무것도 하지 않고 끝낸다.

3.  부모루트 중 더 작은 루트를 최종루트로 삼는다.

4.  더 큰 루트에 최종루트를 저장하고, root[최종루트] 자리에는 현재 root[pa]&root[pb]를 저장한다. &연산을 사용하면 둘 중에 하나라도 false인 경우 false가 반환되므로 이미 트리가 아닌 그래프와 합치는 경우를 거를 수 있다.

5.  더 큰 루트는 최종루트에 합쳐졌으므로 root[더 큰 루트]에 false를 저장한다.

private static void union(int a,int b) {
   int pa = find(a);
   int pb = find(b);
   if(pa==pb) {
      if(a!=b) root[pa] = false;
      return;
   }

   if(pa<pb) {
      set[pb] = pa;
      root[pa] = root[pa]&root[pb];
      root[pb] = false;
   }
   else {
      set[pa] = pb;
      root[pb] = root[pa]&root[pb];
      root[pa] = false;
   }
}

---

3. 결과

다음 부분을 고려하지 않아서 틀렸다.

1.  자기자신이 간선으로 주어지는 경우를 고려하지 않았다.

2.  이미 트리가 아닌 그래프와 합치는 경우도 트리가 아님을 고려하지 않았다.