[백준] 2606번: 바이러스 - Kotlin[코틀린]

문제

 

2606번: 바이러스

 

---

풀이

 

 이러한 문제들의 graph는 2차원 ArrayList로 만들 수 있다. 연결되어 있는 컴퓨터 번호 쌍을 각각의 ArrayList에 추가해준다. 1번 컴퓨터와 연결되어있는 컴퓨터들을 찾는 문제로 1번 컴퓨터부터 시작하는 BFS와 DFS로 해결하는 문제이다.

 

 BFS로 해결하는 경우 Queue<ArrayList>를 이용한다. 큐에서 꺼낸 ArrayList에 연결되어있는 번호가 방문한 적이 없다면, 그 번호로 시작하는 ArrayList를 queue에 추가해주고 cnt는 +1 해준다.

 

 DFS로 해결하는 경우에는 ArrayList에 연결되어있는 번호가 방문한 적이 없다면, DFS를 재귀로 호출해주고 cnt는 +1 해준다.

 

---

코드

 

- BFS

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val vertex = br.readLine().toInt()
    val edge = br.readLine().toInt()
    val graph = ArrayList<ArrayList<Int>>()
    val visited = BooleanArray(vertex+1)
    var cnt = 0

    repeat(vertex+1) {
        graph.add(ArrayList())
    }
    for(i in 0 until edge) {
        val line = StringTokenizer(br.readLine())
        val (v1, v2) = arrayOf(line.nextToken().toInt(), line.nextToken().toInt())
        graph[v1].add(v2)
        graph[v2].add(v1)
    }

    fun bfs(start: Int) {
        val queue : Queue<ArrayList<Int>> = LinkedList()
        queue.add(graph[start])

        visited[start] = true

        while (queue.isNotEmpty()) {
            val cur = queue.poll()

            for(next in cur) {
                if(!visited[next]) {
                    visited[next] = true
                    cnt++
                    queue.add(graph[next])
                }
            }
        }
    }

    bfs(1)

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}

 

- DFS

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val vertex = br.readLine().toInt()
    val edge = br.readLine().toInt()
    val graph = ArrayList<ArrayList<Int>>()
    val visited = BooleanArray(vertex+1)
    var cnt = 0

    repeat(vertex+1) {
        graph.add(ArrayList())
    }
    for(i in 0 until edge) {
        val line = StringTokenizer(br.readLine())
        val (v1, v2) = arrayOf(line.nextToken().toInt(), line.nextToken().toInt())
        graph[v1].add(v2)
        graph[v2].add(v1)
    }

    fun dfs(cur: Int) {
        visited[cur] = true

        for(next in graph[cur]) {
            if(!visited[next]) {
                cnt++
                dfs(next)
            }
        }
    }

    dfs(1)

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}