[알고리즘] 창용 마을 무리의 개수

 

나의 풀이

- connected components를 찾는 문제였다.

- 로직은 크게 두 단계이다.

- 시작할 위치를 정하고 dfs를 돌린다. 이때 방문되는 노드는 모두 하나의 무리가 된다.

- 이를 반복하며 모든 노드가 방문 상태가 될때까지 진행한다. 

- 메소드로 세분화하여 메소드를 구현하였다.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.io.FileInputStream;

// 방문하지 않은 노드 중 하나를 잡아서 bfs를 실행, 이걸 하며 방문한 노드를 묶으면 하나의 무리가 된다.
// 이를 모든 노드를 방문할 때까지 반복한다.
class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
            int M = sc.nextInt();
            
            // 내가 원하는 자료구조는 adjcent list
            ArrayList<Integer>[] graph = new ArrayList[N+1];
            for (int j = 1; j <= N; j++) {
				graph[j] = new ArrayList<>();
            }            
            for (int i = 0; i < M; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
            	
                graph[a].add(b);
                graph[b].add(a);
            }
            
            HashMap<Integer, Boolean> visited = new HashMap<>();
            for (int i=1; i<=N; i++) {
            	visited.put(i, false);    
            }
            
            int count = 0;
            while (!isAllVisited(visited)) {
                count++;
                int startPoint = findStartPoint(visited);
            	dfs(graph, visited, startPoint);
            }
			
            System.out.println("#" + test_case + " " + count);
        }
	}
    
    private static void dfs(ArrayList<Integer>[] graph, HashMap<Integer, Boolean> visited, int startPoint) {
        
        visited.put(startPoint, true);
        int curPoint = startPoint;
        for (int nextPoint : graph[curPoint]) {
            if (visited.get(nextPoint)) {
                    continue;    
            }
			visited.put(nextPoint, true);
            dfs(graph, visited, nextPoint);
          }
    }
    
    private static int findStartPoint(HashMap<Integer, Boolean> visited) {
        for (int person : visited.keySet()) {
        	if (!visited.get(person)){
            	return person;    
            }
        }
        return 0;
    }
    
    private static boolean isAllVisited(HashMap<Integer, Boolean> visited)  {
        for (int person : visited.keySet()) {
        	if  (!visited.get(person)) {
            	return false;    
            }
        }
        return true;
    }
}

 

배운 점

- HashMap.put()으로도 원래있던 키에 대한 value가 갱신된다는 것을 알았다. update 메소드가 따로 없다.

- 아래와 같은 코드는 배열만 만드는 초기화 코드로 각각 안의 값들을 초기화해줘야 한다는 것을 알았다. 이걸 하지 않으면 graph[1]은 null 값과 같다.

ArrayList<Integer>[] graph = new ArrayList[N+1];

- 수정하면 다음과 같다.

ArrayList<Integer>[] graph = new ArrayList[N+1];
for (int j = 1; j <= N; j++) {
    graph[j] = new ArrayList<>();
}

- Queue<> interface의 구현체 중 하나가 LinkedList이다.

- java는 Deque<> interface의 구현체도 제공하는데 그 중 하나가 ArrayDeque이다.

 

더 개선해볼 점

- 1. 인풋을 받는 방식을 buffer로 바꾸면 더 빨라진다고 한다.

- 2. 이것의 시간 복잡도는 어떻게 될까? 더 개선할 수 있는 방법이 있을까?

- 3. bfs로도 바꿀 수 있을까? dfs와 bfs 중 어떤 방법이 더 좋을까?

 

시간 복잡도

- DFS의 로직에서 최악의 경우 모든 엣지와 노드를 돌게 되므로 O(V+E)이다. 

- 이걸 while문이 감싸고 있는데 매 iter마다 하나의 노드는 무조건 진행이 되므로 최악의 경우(모든 노드가 각각 연결이 안된 경우) N번만큼 진행된다.

- 따라서 O(N * (V+E))이 된다. 그런데 문제의 조건에 따라 0 ≤ M ≤ N(N-1)/2 이므로 O(N * N(N-1)/2)  = O(N^3)이 된다. 

- bfs도 시간 복잡도는 마찬가지므로 O(N^3)이 된다. 따라서 시간적으로는 차이가 없다.

 

1번 bufferedReader로 입출력을 받게 되면 다음과 같다.

StringTokenizer는 한 줄을 받을 때마다 new StringTokenizer로 초기화해주어야 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

// 방문하지 않은 노드 중 하나를 잡아서 bfs를 실행, 이걸 하며 방문한 노드를 묶으면 하나의 무리가 된다.
// 이를 모든 노드를 방문할 때까지 반복한다.
class Solution
{
	public static void main(String args[]) throws Exception
	{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int T;
		T=Integer.parseInt(st.nextToken());

		for(int test_case = 1; test_case <= T; test_case++)
		{

			st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            // 내가 원하는 자료구조는 adjcent list
            ArrayList<Integer>[] graph = new ArrayList[N+1];
            for (int j = 1; j <= N; j++) {
				graph[j] = new ArrayList<>();
            }            
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
            	
                graph[a].add(b);
                graph[b].add(a);
            }
            
            HashMap<Integer, Boolean> visited = new HashMap<>();
            for (int i=1; i<=N; i++) {
            	visited.put(i, false);    
            }
            
            int count = 0;
            while (!isAllVisited(visited)) {
                count++;
                int startPoint = findStartPoint(visited);
            	dfs(graph, visited, startPoint);
            }
			
            System.out.println("#" + test_case + " " + count);
        }
	}
    
    private static void dfs(ArrayList<Integer>[] graph, HashMap<Integer, Boolean> visited, int startPoint) {
        
        visited.put(startPoint, true);
        int curPoint = startPoint;
        for (int nextPoint : graph[curPoint]) {
            if (visited.get(nextPoint)) {
                    continue;    
            }
			visited.put(nextPoint, true);
            dfs(graph, visited, nextPoint);
          }
    }
    
    private static int findStartPoint(HashMap<Integer, Boolean> visited) {
        for (int person : visited.keySet()) {
        	if (!visited.get(person)){
            	return person;    
            }
        }
        return 0;
    }
    
    private static boolean isAllVisited(HashMap<Integer, Boolean> visited)  {
        for (int person : visited.keySet()) {
        	if  (!visited.get(person)) {
            	return false;    
            }
        }
        return true;
    }
}

 

3번 dfs를 bfs로 바꾸면 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 방문하지 않은 노드 중 하나를 잡아서 bfs를 실행, 이걸 하며 방문한 노드를 묶으면 하나의 무리가 된다.
// 이를 모든 노드를 방문할 때까지 반복한다.
class Solution
{
	public static void main(String args[]) throws Exception
	{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int T;
		T=Integer.parseInt(st.nextToken());

		for(int test_case = 1; test_case <= T; test_case++)
		{

			st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            // 내가 원하는 자료구조는 adjcent list
            ArrayList<Integer>[] graph = new ArrayList[N+1];
            for (int j = 1; j <= N; j++) {
				graph[j] = new ArrayList<>();
            }            
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
            	
                graph[a].add(b);
                graph[b].add(a);
            }
            
            HashMap<Integer, Boolean> visited = new HashMap<>();
            for (int i=1; i<=N; i++) {
            	visited.put(i, false);    
            }
            
            int count = 0;
            while (!isAllVisited(visited)) {
                count++;
                int startPoint = findStartPoint(visited);
            	bfs(graph, visited, startPoint);
            }
			
            System.out.println("#" + test_case + " " + count);
        }
	}
    
    private static void bfs(ArrayList<Integer>[] graph, HashMap<Integer, Boolean> visited, int startPoint) {
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startPoint);
        visited.put(startPoint, true);
        
        while (!queue.isEmpty()) {
        	int curPoint = queue.poll();
            
            for (int nextPoint : graph[curPoint]) {
                if (!visited.get(nextPoint)) {
                    queue.add(nextPoint);
                    visited.put(nextPoint, true);
                }
        	}
      }
}
    
    private static int findStartPoint(HashMap<Integer, Boolean> visited) {
        for (int person : visited.keySet()) {
        	if (!visited.get(person)){
            	return person;    
            }
        }
        return 0;
    }
    
    private static boolean isAllVisited(HashMap<Integer, Boolean> visited)  {
        for (int person : visited.keySet()) {
        	if  (!visited.get(person)) {
            	return false;    
            }
        }
        return true;
    }
}

 

Reference

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

SW Expert Academy

https://www.geeksforgeeks.org/efficiently-reading-input-for-competitive-programming-using-java-8/

Efficiently Reading Input For Competitive Programming using Java 8 - GeeksforGeeks