[백준] 11724번 연결 요소의 개수 - JAVA

 

 

 

 

 

✍️풀이방식

 

 

1. 문제 분석 

 

1. 노드의 개수가 1000개 
2. N 제곱이면 1000000, 백만 정도면 3초안에 충분히 풀린다. 
3. 양 끝 점 u ,v  같은 엣지는 한번만 주어짐 -> 방향성이 없다 따라서 양쪽 인접리스트로 구현해야한다. 
4.트리 완전 탐색 문제 따라서 DFS로 접근해야한다. 

 

 

 

2. 현재 출력에선 첫째 줄에 연결 요소의 개수를 출력한다고 되어있다. 이는 실제 그래프가 몇 개로 나눠지는 지 즉

몇개의 연결 요소로 구성되는 지 묻고 있다 

 

 

 

예제 입력 1번에선 다음과 같이 나누어진다. 그림으로도 확인할 수 있다.

 

 

 

예제 입력 2번도 1번과 같이 확인할 수 있다. 

 

 

 

 

 

 

 

 

 ⭐따라서 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다. 

 

 

 

 

DFS를 구현하기 위해서 사용해야하는 것

 

1. 인접 리스트

2. 방문 배열 

3. 재귀 형식 

 

 

 DFS 슈도 코드 

DFS{

 if(현재 노드 == 방문 노드) return  (이미 방문한 노드면 DFS를 실행하지 않는다) 
 visited (배열에 현재 노드 방문 기록하기)
 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기 (재귀 함수 형태)
 
 }

 

 

 

 

 

---

 

 

 

🖥️문제풀이

 

 

import java.util.*; 
import java.io.*;

public class Main
{
    
    static boolean visited[]; 
    static ArrayList<Integer>[] A; 
    
	public static void main(String[] args) throws IOException {
		
		BufferedReader br
		= new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st= new StringTokenizer(br.readLine()); 
		
		int n= Integer.parseInt(st.nextToken()); // 노드 개수 입력 
		int m= Integer.parseInt(st.nextToken()); // 엣지 개수 입력 
		
	    visited = new boolean[n+1];
	    
		
		A = new ArrayList[n+1]; // 인접리스트 배열 선언 
		
		for(int i=1; i<n+1; i++){
		    A[i] = new ArrayList<Integer>(); // 인접리스트의 arrylist 초기화 
		    
		}
		
		
		for(int i=0; i<m;i++){
		    
		    st = new StringTokenizer(br.readLine()); // 한줄씩 받기
		    int s= Integer.parseInt(st.nextToken()); // 시작점 입력 
		    int e= Integer.parseInt(st.nextToken()); // 종료점입력 
		    
		    A[s].add(e);
		    A[e].add(s); // 방향성이 없고 연결되어있기 때문에 
		    
		}//노드의 개수 만큼 엣지 정보들 받기 
		
		
		int count = 0; 
		
		for(int i=1 ;i<n+1;i++){
		    
		    if(!visited[i]){// 방문하지 않은 노드 
		       
		        count ++; 
		        DFS(i);
		        
		    }
		    
		}
		
		
		System.out.println(count); 
	
	
 	}
 	
 	
 	private static void DFS (int v){
 	    
 	    if(visited[v]) return; // 현재 노드가 방문 노드면 바로 종료 
 	    
 	    visited[v] = true; // 현재 노드 방문 노드로 기록 
 	    
 	    for(int i: A[v]){ //A[v] 안에 들어 있는 원소들을 하나씩 꺼내서 i에 넣는다
 	        if(!visited[i]){
 	            DFS(i); 
 	        }
 	    }
 	    
 	}
 
}