[JAVA] 4803번 - 트리

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제 해석)

문제에서 주어진 테스트케이스 3개를 그려보면 이렇다.

이렇게 트리의 개수를 세어야한다.

++ 사이클이 하나, 트리가 하나 있는 경우는 어떻게해야하나 싶었는데 반례케이스를 보니 이 경우는 트리가 1개이다.

즉 하나의 케이스에 사이클이 존재해도, 나머지 트리의 개수만 신경쓰면 된다 

 

 

문제 아이디어)

BFS로 시도했다. 그리고 처음에 고민한게 사이클인지 판단하는 코드가 필요하고, 그 외에 또 트리를 세고,,, 하면 너무 복잡할 것 같았다. 그래서 트리의 정의를 활용했다.

트리의 사이클이 없고, 모든 노드가 연결된다면 

트리는 정점이 N개, 간선이 N-1개 이다.

 

그래서 이걸 활용했다. 1번 노드부터 N번노드까지 반복문을 돌면서 BFS를 실행한다.

그럼 해당 예시처럼 첫번째 케이스는 3번 BFS호출하고, 1번 호출, 2번 호출하게된다.

그리고 트리인지 확인한다. 트리의 정의를 이용해 간선과 노드의 갯수로 트리인지 확인 

트리라면 1을 반환, 아니라면 0을 반환해서

3번째 같은 경우는 모두 트리가 아니니까 0을 반환 -> No Tree가 된다

그리고 싸이클 하나, 트리 하나 이렇게 있는 경우 1을 반환 -> 트리 한개 

첫번째 경우 3번 호출하고 3번 다 트리니까 3반환 -> 트리3개 

이렇게 로직이 될것이고 이렇게 구현하면 된다!!

 

 

 

시간복잡도

인접리스트로 구현했다.

인접리스트의 경우 시간복잡도는 O(V+E)이다.

V는 최대 500, N은 최대 124750

O(125250)으로 1초안에 충분히 가능하다! 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 입력받기

-> 0 0 이나올때까지 입력받았다.

while(!(str=br.readLine()).equals("0 0"))

 

2. 트리인지 확인하는 함수

-> 트리면 1을 반환한다. 트리가 되려면 Edge/2 == node-1 이되어야 트리이다.

2를 나누는 이유는 양방향 그래프가 아닌 무방향 그래프이기 때문이다. 그래서 2로 나누어야 실제 간선수다.

1을 빼는 이유는 트리에서 간선 수는 노드 수보다 항상 1이 적다. 

 

bfs를 통해, 방문하는 노드를 카운팅하고, 이어진 노드의 간선을 카운팅하여 트리인지 확인한다

private static int checkTree(int x) {
		Queue<Integer>q = new LinkedList<Integer>();
		
		int node = 0;
		int edge = 0;
		
		q.add(x);
		visited[x] = true;
		while(!q.isEmpty()) {
			int tmp = q.poll();
			node++;
		
			for(int next: adj[tmp]) {
				edge++;
				if(!visited[next]) {	
					visited[next] = true;
					q.add(next);
					
				}
			}
			
		}
		
		return edge / 2 == node - 1 ? 1 : 0;
	}

 

 

3. 트리확인하기

-> 트리의 갯수를 더해서 출력

int tree=0;
        	for(int i=1; i<=n; i++) {
        		if(!visited[i]) {
        			tree+=checkTree(i);
        		}
        	}

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int n,m;
	static boolean[] visited;
	static LinkedList<Integer>[] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str = null;
        int testCase=1;
        
        while(!(str=br.readLine()).equals("0 0")) {
        	
        	String[] input = str.split(" ");
        	n = Integer.parseInt(input[0]);
        	m = Integer.parseInt(input[1]);
        	
        	adj = new LinkedList[n+1];
        	for(int i=1; i<=n; i++ ) {
        		adj[i] = new LinkedList<Integer>();
        	}
        	visited = new boolean[n+1];
        	
        	StringTokenizer st;
        	for(int i=0; i<m; i++) {
        		st = new StringTokenizer(br.readLine());
        		int u = Integer.parseInt(st.nextToken());
        		int v = Integer.parseInt(st.nextToken());
        		
        		adj[u].add(v);
        		adj[v].add(u);
        	}
        	
        	
        	int tree=0;
        	for(int i=1; i<=n; i++) {
        		if(!visited[i]) {
        			tree+=checkTree(i);
        		}
        	}
        	
        	
        	
        	System.out.print("Case " + testCase + ": ");;
        	if(tree>1) {
        		System.out.println("A forest of " + tree + " trees.");
        	}
        	else if(tree==1) {
        		System.out.println("There is one tree.");
        	}
        	else {
        		System.out.println("No trees.");
        	}
        	
        	testCase++;
        	
        }
 
    }
	private static int checkTree(int x) {
		Queue<Integer>q = new LinkedList<Integer>();
		
		int node = 0;
		int edge = 0;
		
		q.add(x);
		visited[x] = true;
		while(!q.isEmpty()) {
			int tmp = q.poll();
			node++;
		
			for(int next: adj[tmp]) {
				edge++;
				if(!visited[next]) {	
					visited[next] = true;
					q.add(next);
					
				}
			}
			
		}
		
		return edge / 2 == node - 1 ? 1 : 0;
	}
	
	}