[JAVA] 연결 요소의 개수

문제 탐색하기

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

 

그림을 그려보면 어떻게 접근을 해야하는지 금방 알 수 있다.
첫번째, 두번째 예시를 그린건데 이 문제의 정답은 그래프의 갯수를 구하면된다!

그래프의 갯수를 구하려면 DFS연산이 끝날때 1을 증가해주면된다!!!!

그리고 인접리스트를 이용했다

 

시간복잡도

인접리스트를 이용한 DFS를 구현했으니까 O(N+M)이다!

O(1000+499,500) = O(500,500)이다 

 

그리고 이 문제를 풀기 위한 핵심은 어떻게 한 그래프의 DFS탐색이 끝날때 카운트를 할것인가? 이다

 

 

코드 설계하기

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

1.그래프를 만든다

2. DFS연산을 수행한다

3. 출력 

 

시도 회차 수정 사항

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

 

1회차 시도

=> 정점의 수만큼 반복문을 돌면서 카운트를 시작하고 dfs를 수행했다

이렇게하면 그냥 정점의 수만큼 출력된다 

for(int i=1; i<=n; i++) {
        	cnt++;
        	dfs(i);
        }
        System.out.println(cnt);
        
    }

	private static void dfs(int i) {
		isVisited[i] = true;
		
		for(int j :adjList[i]) {
			if(!isVisited[j]) {
				dfs(j);
			}
		}

 

2회차 시도

=> DFS문에 if문으로 방문한 경우 카운트를 햇는데 정답이 아니었다

dfs(1);
        System.out.println(cnt);
        
    }

	private static void dfs(int i) {
		isVisited[i] = true;
		
		for(int j :adjList[i]) {
			if(!isVisited[j]) {
				dfs(j);
			}
			else if(isVisited[j]) {
				System.out.println(j);
				cnt++;
			}
		}

 

정답코드

=> 정점의 수 만큼 반복문을 돌면서 방문하지 않은 정점인경우 dfs를 시작하고 카운트를 했다

그러면 첫번째 예시에서 정점 1이 시작될때 한번 카운트 되고 새로운 그래프 정점3이 시작될때 또 한번 카운트 되니까 정답이다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static LinkedList<Integer>[] adjList;
	static boolean[]isVisited;
	 static int cnt = 0;
	
    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());
        
        isVisited = new boolean[n+1];
        adjList = new LinkedList[n+1]; 
        
        for(int i=0; i<=n; i++) {
        	adjList[i] = new LinkedList<Integer>();
        }
        
        //그래프 구현
        for(int i=0; i<m; i++) {
        	st = new StringTokenizer(br.readLine());
        	int u = Integer.parseInt(st.nextToken());
        	int v = Integer.parseInt(st.nextToken());
        	
        	adjList[u].add(v);
        	adjList[v].add(u);
        }
        
       
        for(int i=1; i<=n; i++) {
        	if(!isVisited[i]) {
        		dfs(i);
        		cnt++;
        	}
        }
        System.out.println(cnt);
        
    }

	private static void dfs(int i) {
		isVisited[i] = true;
		
		for(int j :adjList[i]) {
			if(!isVisited[j]) {
				dfs(j);
			}
			
		}
	}
}