백준 2606-바이러스(Kotlin)

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

2606번: 바이러스

 

문제 접근

딱 그래프 탐색을 할 수 있는지를 물어보는 문제

 

시간복잡도

인접 리스트를 활용한dfs로 계산시 O(V+E)인데, 간선이 얼마나 주어지는 지를 모르겠다..

인접 행렬로 구현하면 O(V^2)인데, 이때 V(노드, 여기선 컴퓨터의 수)는 100이하니깐 100^2으로 여유롭다.

그보다도 O(V+E)가 더 작으니깐 어떤걸쓰든 그래프 탐색을 할 줄 아느냐를 물어보는 문제인듯

 

인접리스트 + DFS로 구현

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

var n = 0
var g = Array(n+1){ArrayList<Int>()}
val check = BooleanArray(1001)
var count = 0
fun main(args: Array<String>): Unit = with(Scanner(System.`in`)) {
   n = nextInt()
    g = Array(n+1){ArrayList<Int>()}
    val edge = nextInt()
    for (i in 0 until edge){
        val a = nextInt()
        val b = nextInt()
        graph(a,b)
    }
    dfs(1)
    //1번과 연결되어있는 컴퓨터의 수를 구하시오(1번 제외)
print(count)
}

fun graph(a:Int, b:Int){
    g[a].add(b)
    g[b].add(a)
}
fun dfs(start:Int){
    check[start] = true

    for (i in 1..n){
        if (g[i].contains(start) && !check[i]){
            count++
            dfs(i)
        }
    }
}