Today I Learned

간만에 leetcode 자바 말고 백준 kotiln 문제를 풀어봤다.

연결 요소의 개수

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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

• 입력
  첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
• 출력
  첫째 줄에 연결 요소의 개수를 출력한다.
• 예시
  입력
  6 5
  1 2
  2 5
  5 1
  3 4
  4 6
  출력 2

풀이 과정

• 그래프의 연결 여부를 확인할 때 연결된 모든 노드를 탐색하기 위해 BFS를 사용해 문제를 풀었다.

1. 그래프 생성
   입력으로 주어진 노드 수(n)와 간선 수(m)를 받습는다. 인접 리스트 형태의 그래프를 생성하는데, 2차원을 배열과 list로 그래프를 구현한다. 각 노드의 인접한 노드들을 저장하기 위해 MutableList\ 형태의 리스트를 사용했다.

2. 간선 정보 저장
   선의 정보를 입력으로 받아서 그래프에 저장한다. 주어진 간선은 양방향이므로, 양쪽 방향에 모두 노드 정보를 추가한다.

3. BFS를 통한 탐색
   모든 노드를 순회하면서 방문하지 않은 노드에 대해 BFS를 수행한다. 그 동안 방문한 노드를 표시하기 위해 visited 배열을 사용한다.

4. 연결 요소 개수 세기
   BFS를 수행할 때마다 연결된 요소를 찾고, 새로운 연결 요소를 찾을 때마다 카운트를 증가시킨다.
   연결된 요소의 개수를 출력하면 완료!

Kotlin 코드

import java.util.*

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val graph = Array(n + 1) { mutableListOf<Int>() }
    val visited = BooleanArray(n + 1) { false }

    repeat(m) {
        val (u, v) = readln().split(" ").map { it.toInt() }
        graph[u].add(v)
        graph[v].add(u)
    }

    var count = 0
    for (i in 1..n) {
        if (!visited[i]) {
            bfs(graph, visited, i)
            count++
        }
    }

    println(count)
}

fun bfs(graph: Array<MutableList<Int>>, visited: BooleanArray, start: Int) {
    val queue: Queue<Int> = LinkedList()
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        for (adjNode in graph[node]) {
            if (!visited[adjNode]) {
                queue.add(adjNode)
                visited[adjNode] = true
            }
        }
    }
}