[백준]11724 연결 요소의 개수 - 자바/Java

11724번: 연결 요소의 개수

🌱풀이

알고리즘

1. 연결 요소의 개수가 무엇인지 알아야 풀 수 있다. 서로 연결된 에지들은 하나로 취급한다. 즉 연결되지 않은 독립된 에지 그룹이 몇 개인지 묻는 문제다.
2. 재귀 함수 구조를 이용한 깊이 우선 탐색 DFS를 구현했다.
3. 그래프 구현에는 3가지 방법이 있다. 에지 리스트, 인접 행렬, 인접 리스트. 이 중 인접 리스트는 구현이 가장 까다롭지만, 성능이 가장 뛰어나다. 그래서 인접 리스트를 적용했다.
4. 인접 리스트는 ArrayList 배열을 선언하여 그래프를 표현한다. 선언 과정을 유심히 보면 좋다.
5. 한 번 탐색한 곳은 탐색하지 않으므로 boolean형 visited[] 을 선언하여 조건문에 활용한다.
6. 가장 기본적인 형태의 재귀함수 이므로 이해하고 외워두기.

메모리 : 144688KB, 시간 : 644ms

package book_algoTEst;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_11724 {
	static ArrayList<Integer>[] A;
	static boolean visited[];
	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());
		A = new ArrayList[n+1];
		visited = new boolean[n+1];
		for(int i = 1; i<n+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		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); // dfs 함수 호출하기 -> 재귀적으로 구성할 것
			}
		}
		System.out.print(count);
	}
	static void DFS(int v) {
		if(visited[v]) return; //거쳐간 엣지는 더 이상 진행하지 않음
		visited[v] = true; //다녀간 곳으로 표시하기
		for(int i : A[v]) { // 향상된 for문
			if(visited[i] == false) DFS(i); //다녀가지 않았던 곳만 탐색하기
		}
	}
}

---

🪴코드 리뷰

🌿메모리 : 343384KB, 시간 : 2732ms

이건 내가 옛날에 풀었던 코드인데, DFS가 아니라 BFS로 풀었다. 풀리긴 할거다. 정점의 개수가 1000개 이하이므로 시간 복잡도가 N 제곱이 되어도 통과는 할 수 있다. 하지만 시간과 메모리에서 볼 수 있듯이 성능이 좋진 않다. 게다가 그래프를 LinkedList로 구현하여, 성능이 더 악화됐다.

💡 풀이자 : 본인

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 정점의 개수
		int M = sc.nextInt(); // 간선의 개수
		int cnt = 0;
		Queue<Integer> q = new LinkedList<>();
		LinkedList<Integer>[] graph = new LinkedList[N + 1];
		for (int i = 0; i < N + 1; i++) {
			//항상 자기 자신이 포함되어야 하는구나..................
			graph[i] = new LinkedList<>();
			graph[i].add(i);
		}
		for (int i = 0; i < M; i++) {
			int Node = sc.nextInt();
			int Con = sc.nextInt();
			graph[Node].add(Con);
			graph[Con].add(Node);
		}

		for (int i = 1; i < N + 1; i++) {
			// 해당 노드에 연결된 간선이 있다면 (다른 노드가 저장되어 있다면)
			// Queue를 사용하여 모두 저장해준다.
			// while문을 이용하여 카운트 해줄 것임
			if (graph[i].size() != 0) {
				for (int j = 0; j < graph[i].size(); j++) {
					q.add(graph[i].get(j));
				}
				while (graph[i].size() != 0) {
					graph[i].remove();
				}
				// 연결된 간선을 돌면서 모두 지워버린다.
				while (!q.isEmpty()) {
					int cur = q.poll();
					for (int j = 0; j < graph[cur].size(); j++) {
						q.add(graph[cur].get(j));
					}
					while (graph[cur].size() != 0) {
						graph[cur].remove();
					}
				}
				cnt++;
			}
		}
		System.out.println(cnt);
		sc.close();
	}
}

---

🌿메모리 : 118760KB, 시간 : 520ms

아래처럼 표현한 그래프는 인접 행렬이라고 한다. 인접 행렬의 특징은 최대 에지의 크기만큼 nXn 배열을 선언하여 에지들의 간선 관계를 표현한다는 것이다. 구현이 간편하다. 상황에 따라선 인접 리스트보다 성능이 좋을 순 있겠다.

💡 풀이자 : qjrjgud

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] arr;
    static int[] check;
    static int n, m, cnt = 0;

    public static void dfs(int a) {
        check[a] = 1;
        for (int i = 1; i <= n; i++) {
            if (arr[a][i] == 1 && check[i] != 1) {
                check[i] = 1;
                dfs(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n + 1][n + 1];
        check = new int[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == 0) {
                dfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

---

🌿메모리 : 115232KB, 시간 : 456ms

아 BFS로 풀어도 잘 되는구나 ㅋㅋㅋㅋ (머쓱) BFS 풀이는 Queue를 이용해서 에지 주변의 간선을 탐색하고, DFS 풀이는 Stack(재귀)를 이용해서 에지에 연관된 에지를 파고들며 탐색한다. 결국 둘 다 완전 탐색의 일종이므로 문제 풀이에는 만족한다.

💡 풀이자 : etminho12

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static boolean[][] adj;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new boolean[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            adj[u][v] = true;
            adj[v][u] = true;
        }

        visited = new boolean[N + 1];
        int result = 0;

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                bfs(i);
                result++;
            }
        }
        System.out.println(result);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        // 방문 처리
        visited[start] = true;

        while (!queue.isEmpty()) {
            int v = queue.poll();

            for (int i = 1; i <= N; i++) {
                if (adj[v][i] && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }

        }

    }
}

---

Conclusion

• 그래프를 표현하는 세가지 방식에 대해서 숙지해두면 상황에 맞게 표현할 수 있다.
• 귀찮음을 감수할 때 가장 크게 성장함을 기억하기!