[백준 2606번] [Kotlin] 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

난이도 : 실버 3
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

---

설명

 

DFS 혹은 BFS를 이용해 연결된 노드의 갯수를 구하는 문제입니다.

 

DFS, BFS 어느 것을 사용해도 무방하나 DFS를 많이 사용해봤기에 이번엔 BFS를 사용해 풀이해보겠습니다.

 

---

소스코드

 

인풋값 저장

val n = readLine()!!.toInt()
val bridgeCnt = readLine()!!.toInt()

val map = Array(n + 1) { Array(n + 1) { false } }

repeat(bridgeCnt) {
    val input = readLine()!!.split(" ")
    val x = input[0].toInt()
    val y = input[1].toInt()
    map[x][y] = true
    map[y][x] = true
}

 

map은 서로 연결되어있는지 여부를 담는 배열입니다.

 

예를 들어 map[1,2] = true라면 1번 컴퓨터와 2번 컴퓨터가 연결되어 있다는 의미입니다.

 

1번이 2번 컴퓨터와 연결되어 있다는건, 2번이 1번과 연결되있다는 것과 동일한 의미이므로,

map[x][y]가 true라면 map[y][x] 역시 true로 바꿔줍니다.

 

 

문제에서 첫 컴퓨터의 번호가 1부터 시작하기에,

 

배열의 idx와 컴퓨터의 번호를 맞추기 위해 map의 크기를 n+1만큼 지정해주었습니다.

 

BFS

fun bfs(n: Int, map: Array<Array<Boolean>>) {

    val q: Queue<Int> = LinkedList()
    val visited = Array(n + 1) { false }
    visited[1] = true

    q.offer(1)

    var cnt = 0

    while (q.isNotEmpty()) {
        val target = q.poll()

        for(i in map.indices) {
            if(!visited[i] && map[target][i]) {
                q.offer(i)
                visited[i] = true
                cnt++
            }
        }
    }

    println(cnt)
}

 

bfs에 쓰일 큐를 하나 만들고,

각 노드의 방문 여부를 담을 visited 배열 역시 만들어줍니다.

 

1번 컴퓨터와 연결된 노드를 찾는것이 목적이기에,

 

모든 케이스에 대해 1번을 시작점으로 bfs를 하면 되므로

큐에 첫번째로 1번 컴퓨터를 넣어주고 방문을 했다는 의미로 visited[1]을 true로 바꿔줍니다.

 

.

 

while (q.isNotEmpty()) {
    val target = q.poll()

    for(i in map.indices) {
        if(!visited[i] && map[target][i]) {
            q.offer(i)
            visited[i] = true
            cnt++
        }
    }
}

이후, 큐에서 하나를 꺼내 해당 큐에 연결된 노드를 모두 큐에 넣고,

연결된 노드를 방문처리(visited[i] = true) 합니다.

 

방문한 노드를 카운트하기 위해 cnt를 1만큼 증가시켜 주고,

 

이 작업을 큐가 빌 때 까지 반복하면 됩니다.

 

 

 

bfs(n, map)

 마지막으로 위에서 구현한 bfs를 main()에서 호출하면 끝입니다.

---

후기

dfs/bfs를 이용해 연결된 노드가 몇개인지 구하는 문제였습니다.

 

첨에 낯설었던 그래프 탐색도 이제 점차 익숙해져 가네요.