BOJ_11724 : 연결 요소의 개수

👉 문제링크

11724번: 연결 요소의 개수

---

---

🔸 문제 분석 🔸

• n개의 정점 사이의 간선의 정보가 m개 입력된다.
  • 연결된 노드의 묶음(연결 요소) 수를 출력한다.
• n개의 각 노드를 시작으로 BFS 혹은 DFS로 연결된 노드를 체크한다.
  • 여기서는 BFS를 사용한다.
  • BFS를 위해 큐와 visit 배열을 사용한다.
  • visit 배열에 방문하지 않으면 0, 방문하면 묶음 번호를 저장한다. (0만 아니면 된다.)
• 묶음 수를 출력한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) {
        // 1 : input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            if (!graph[u].contains(v))
                graph[u].add(v);
            if (!graph[v].contains(u))
                graph[v].add(u);
        }

        // 2 : BFS
        Queue<Integer> queue = new LinkedList<>();
        int[] visit = new int[n + 1];
        int gruop = 0;
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 0) {
                gruop++;
                queue.add(i);
                while (!queue.isEmpty()) {
                    int now = queue.poll();
                    if (visit[now] == 0) {
                        visit[now] = gruop;
                        for (int g : graph[now]) {
                            queue.add(g);
                        }
                    }
                }
            }
        }
        System.out.println(gruop);
    }
}

🔸 코드 해석 🔸

• 1) 노드 수 n과 간선 수 m을 입력받고, n 크기의 ArrayList 배열 graph를 선언한다.
  • m개의 간선 정보를 입력 받아 graph에 정보를 저장한다.
• 2) BFS를 수행한다.
  • 큐, visit 배열, 그룹 수 변수를 선언한다.
  • 1부터 n번 노드까지 각각 시작노드로 설정해본다.
  • 시작 노드를 방문하지 않았으면 BFS를 수행한다. 
    • 그룹 번호를 +1 한다. 
    • 시작 노드를 큐에 담는다.
    • 큐가 빌 때까지 탐색한다.
      • 큐에에서 값을 하나 poll 한 뒤 now에 저장한다. 
      • 방문한 노드 visit[now] 값이 0이면, 방문하지 않았다는 것이므로 계산을 진행한다.
        • visit[now]에 값을 넣는다(0만 아니면 되지만, 이쁘게 그룹 번호를 넣어주었다.)
        • now번째 노드에 연결된 모든 노드를 큐에 넣어준다.
          • 방문했는지 안했는지 확인해도 되지만, 어차피 visit[now]가 0인지 확인하는 코드가 있으므로 따로 추가하진 않았다.

 

---

🔸 end 🔸

• 오랜만에 BFS문제를 풀어보았는데, 아직 그래프 문제들의 숙련도가 낮은 것 같다.
  • 그래프와 dp를 중심으로 문제를 많이 풀어보아야겠다.
• 각 노드가 어떤 그룹인지 나타내고자 visit을 int[]로 선언했지만, boolean[]이 더 맞는 것 같다.
• 문제 분석 및 코드 계획을 써보고 코딩에 들어갔다.