BOJ_11724_연결 요소의 개수

1

구분: 그래프 이론, 그래프 탐색, BFS, DFS

언어: Java

전략

• 그래프들의 연결 관계를 인접 리스트를 이용하여 표현한다 - Node클래스 생성, Node배열 생성
• 노드 1번 부터 BFS를 통해 차례로 방문을 한다 - 방문 여부 체크 

---

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{

//연결 리스트로 그래프를 받을 예정
	static class Node{
		int node; //노드 자체
		Node link;//연결된 것
		Node(int node, Node link){
			this.node = node;
			this.link = link;
		}
	}
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); //정점 수 
		int m = scanner.nextInt(); //간선 수 
		
		Node[] list = new Node[n+1];
		
        //무방향 그래프
		for(int i = 0; i<m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			list[a] = new Node(b,list[a]);
			list[b] = new Node(a, list[b]);
		}
		
		int cnt = 0;

		Queue<Integer> qq = new LinkedList<>();
		boolean[] check = new boolean[n+1];
        
		for(int i = 1; i<=n; i++) {
			//이미 방문한 정점이라면 지나가 
            if(check[i])continue;
            
            //큐에 넣고 방문 처리
			qq.add(i);
            check[i] = true;
            
            cnt++;
            
			while(!qq.isEmpty()) {
				int num = qq.poll();
				//인접한 부분을 탐색
                for(Node temp = list[num]; temp!=null; temp=temp.link) {
					//이미 방문한 곳이라면 지나가 
                    if(check[temp.node])continue;
					check[temp.node] = true;
					qq.add(temp.node);
				}
			}
		}
		System.out.println(cnt);
		
	}//main
	
}

 

---

3

무방향 그래프인데 DFS를 2번 사용하여 처음에는 시간 초과가 발생하였다 

정점의 개수가 1000개 이하니 인접 행렬로 그래프를 표현해도 될 것 같다