[백준] 11724번 연결 요소의 개 JAVA (자바) 풀이

문제 11724번

 :  연결 요소의 개수 구하기

 

 

 [입력]

 :  첫째 줄에 정점의 개수 N, 간선의 개수 M

 :  둘째 줄부터 M개의 줄에 간선의 양 끝점 u, v(1 ≤ u, v ≤ N, u ≠ v)
   (같은 간선은 한 번만)

 

 

 [출력]

 :  연결 요소의 개수를 출력

 

 

 [설명]

 

 DFS 

 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

 Stack 혹은 재귀함수로 구현

 

• 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가
  더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행
• 모든 노드를 방문하는 경우에 사용

 

 [문제 과정]

 

 

입력	1 2     2 5     5 1     3 4     4 6
출력	2

                         출처 : https://aeunhi99.tistory.com/59

 

 

 

if(!visit[i]){ dfs(i); }  →  if문 시작
	dfs(1)	방문처리	다음 경로	result
1 단계	dfs(1)	visit[1]	arr[1][2]	-
2 단계	dfs(2)	visit[2]	arr[2][5]	-
3 단계	dfs(5)	visit[5]	arr[5][1]	-
4 단계	dfs(1)	-	-	+ 1
if(!visit[i]){ dfs(i); }  →  if문 시작 2
1 단계	dfs(3)	visit[3]	arr[3][4]	-
2 단계	dfs(4)	visit[6]	arr[4][6]	-
3 단계	dfs(6)	-	-	+ 1
결과값  :  result = 2

 

 [DFS 코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M;
    static int arr[][];
    static boolean visit[];
    static int result=0;
    static int x,y;    
    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        visit = new boolean[N+1];
        
        for(int i =1; i<M+1; i++){
                st = new StringTokenizer(br.readLine());
                x=Integer.parseInt(st.nextToken());
                y=Integer.parseInt(st.nextToken());
                arr[x][y] = arr[y][x] = 1;
        }
        
        for(int i=1;i<N+1;i++) {
			if(!visit[i]){
				dfs(i);
                result++;
			}
		}
        System.out.println(result);
    }
    
    public static void dfs(int node){
        visit[node]=true;
        
        for(int i =1; i<N+1; i++){
            if(!visit[i] && arr[node][i]==1){
                dfs(i);
            }
        }
            
    }
    
}

 

 [해설]
     

 :  static int N,M;  정점 수, 연결선 개수
    static int arr[][];  2차원 배열
    static boolean visit[];  방문기록
    static int result=0;  결과 값
    static int x,y;  두번째 줄부터 받는 입력값들

 :  st=new StringTokenizer(br.readLine());  한 줄 입력받기
    N =Integer.parseInt(st.nextToken());  정점 수
    M =Integer.parseInt(st.nextToken());  연결선 수
     

 :  arr = new int[N+1][N+1];  정점 2차원 배열
    visit = new boolean[N+1];  방문기록 배열 
        
 :  for(int i =1; i<M+1; i++){
              st = new StringTokenizer(br.readLine());  한줄씩 끊어읽기
              x=Integer.parseInt(st.nextToken());  둘째줄 입력1
              y=Integer.parseInt(st.nextToken());  둘째줄 입력2
              arr[x][y] = arr[y][x] = 1;   입력받은 값들을 1이라고 가정
    }

 

 :  for(int i=1;i<N+1;i++) {
             if(!visit[i]){  방문 처리만 안된 경우만 dfs 실행
                     dfs(i);  dfs 실행
                     result++;  결과 카운트
             }
    }

 :  System.out.println(result);  결과 출력

                
        
 :  public static void dfs(int node){  초기값 node = i 이다
        visit[node]=true; 방문처리
        
        for(int i =1; i<N+1; i++){
            if(!visit[i] && arr[node][i]==1){ 입력받은 값들(값이 1처리된 애들) 중에 방문처리 안된 경우
                dfs(i);  해당 i dfs에 대입
            }
        }

    }

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *