[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)4803번, 트리

문제 링크

4803번: 트리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

트리 구조 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 그래프의 정보가 입력됩니다.

2. 같은 간선 여러번 주어지지 않습니다.

3. 0 0이 입력되었을 때 입력이 종료됩니다.

 

그래프가 트리인지 확인하기 위해서 사이클이 존재하지 않는지 확인해야합니다.

 

BFS를 통해서 해당 그래프가 사이클이 존재하는지 확인합니다.

사이클이 존재하지 않는다면 해당 그래프가 트리로 확인할 수 있습니다.

테스트 케이스에 적용하여 트리의 개수를 얻습니다.

 

트리의 개수에 따른 결과를 출력합니다.

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 그래프의 정보를 저장합니다.
• 그래프를 BFS탐색으로 사이클이 존재하는지 확인하여 트리인지 확인하는 bfs함수를 실행하였습니다.
• BufferedWriter에 트리의 개수에 따른 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 BFS탐색으로 사이클이 존재하는지 확인하여 그래프가 트리인지 확인하는 함수입니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	static ArrayList<ArrayList<Integer>> graph;	//그래프 정보 저장 리스트
	static boolean[][] lineCheck;	//간선 사용 확인
	static boolean[] visited;		//정점 방문 확인
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st;
    	int count = 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)
    			break;
    		graph = new ArrayList<>();
    		visited = new boolean[n+1];
    		lineCheck = new boolean[n+1][n+1];
    		int treeCount = 0;
            //그래프 정보 초기화
    		for(int i=0;i<=n;i++) 
    			graph.add(new ArrayList<>());
    		//그래프 정보 저장
    		for(int i=0;i<m;i++) {
    			st = new StringTokenizer(br.readLine());
    			int u = Integer.parseInt(st.nextToken());
    			int v = Integer.parseInt(st.nextToken());
    			graph.get(u).add(v);
    			graph.get(v).add(u);
    		}
            //트리인지 BFS를 통해 확인
    		for(int i=1;i<=n;i++) {
    			if(!visited[i])
    				treeCount += bfs(i);
    		}
    		if(treeCount == 0)		//트리가 존재하지 않을 때
    			bw.write("Case " + count + ": No trees.\n");
    		else if(treeCount==1)	//트리가 1개일 때
    			bw.write("Case " + count + ": There is one tree.\n");
    		else		//트리가 1개 이상일 때
    			bw.write("Case " + count + ": A forest of " + treeCount + " trees.\n");
    		
    		count++;
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS를 통해서 사이클 존재하는지 확인하여 트리인지 구분하는 함수
    static int bfs(int start) {
    	Queue<Integer> queue = new LinkedList<>();
    	visited[start] = true;	//시작 방문 확인
    	queue.add(start);
    	while(!queue.isEmpty()) {
    		int cur = queue.poll();
            //그래프 인접한 정점 탐색
    		for(int next : graph.get(cur)) {
            	//사이클 발생시
    			if(visited[next]) {
    				if(!lineCheck[cur][next])
    					return 0;
    			}else {
    				visited[next] = true;
    				lineCheck[cur][next] = true;
    				lineCheck[next][cur] = true;
    				queue.add(next);
    			}
    		}
    	}
    	return 1;	//트리이면 1을 반환
    }
}