[백준 11724] 연결 요소의 개수

 

문제

 

아이디어

정점, 간선 단어를 보자마자 '그래프'?

연결 요소 == 이어진 그래프를 의미한다.

BFS or DFS를 떠올린다.

 

나는 BFS를 선택했다.

모든 노드(정점) 목록을 원소로 갖는 집합(Set)을 두고

한 번의 BFS마다 생기는 그래프를 전체 집합에서 제외시키는 방식으로 풀이했다.

(전체 집합이 공집합이 될 때까지 Loop)

실수

undirected graph (무방향 그래프) 인것을 확인하지 않고

단방향 연결 리스트로만 체크하다가 틀려버렸다.

 

구현

[Graph.kt]

import java.util.*
import kotlin.collections.ArrayList

class Graph(private val vertexNumber: Int) {
    val vertexSet : Set<Int> = (1 .. vertexNumber).toSet()

    //    정점 번호 [1,1000] 따라서 연결 Set +1
    private val adjacencyArray : Array<ArrayList<Int>> = Array<ArrayList<Int>>(vertexNumber+1){ ArrayList<Int>() }

//    '양방향' non-directed Graph인걸 생각 못함
//    ex ) 반례 : 1-2, 3-1 연결 => 그래프 1개 but 내코드 2개 (단방향)
    fun connectEdge (sourceVertex : Int, targetVertex: Int) {
        adjacencyArray[sourceVertex].add(targetVertex)
//    양방향은 다음 한 줄 추가.
        adjacencyArray[targetVertex].add(sourceVertex)
    }

    //    BFS 를 수행하며 연결된 노드들을 한 세트에 담아 리턴함.
    fun bfs (startVertex : Int) : Set<Int> {
        val visited : BooleanArray = BooleanArray(vertexNumber+1)
        val queue : Queue<Int> = LinkedList<Int>()
        val connectedSet : MutableSet<Int> = mutableSetOf()
        visited[startVertex] = true
        queue.add(startVertex)

        while (queue.isNotEmpty()) {
            val targetVertex = queue.poll()
//            정점 집합에서 이미 방문한 것들을 제외시킨다.
            connectedSet.add(targetVertex)
            adjacencyArray[targetVertex].forEach(){
                if (!visited[it]) {
                    queue.add(it)
                    visited[it] = true
                }
            }
        }
        return connectedSet.toSet()
    }
}

 

[Main.kt]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
//    요거 2줄은 그냥 암기하는게 나을듯 ㅋㅋ 띄어쓰기 구분해줌
    val bufferedReader : BufferedReader = BufferedReader(InputStreamReader(System.`in`))
    var token = StringTokenizer(bufferedReader.readLine())

    val vertexNumber : Int = token.nextToken().toInt()
    val edgeNumber : Int = token.nextToken().toInt()

    val graph = Graph(vertexNumber)

    var sourceVertex : Int
    var targetVertex : Int
//    요 아래줄도 그냥 자주쓰임.
    for (i in 0 until edgeNumber) {
       token = StringTokenizer(bufferedReader.readLine())
        sourceVertex = token.nextToken().toInt()
        targetVertex = token.nextToken().toInt()
//        Graph 연결
        graph.connectEdge(sourceVertex, targetVertex)
    }

    var answer : Int = 0
    // 연결된 모든 정점을 갖는다.
    var allNodeSet = graph.vertexSet
    while (allNodeSet.isNotEmpty()) {
        val nodeSet = graph.bfs(allNodeSet.first()).toSet()
        // 전체노드 - 한 번의 BFS로 생성된 그래프 (Component)
        allNodeSet = (allNodeSet subtract nodeSet)
        answer++
    }
    print(answer)

}