[dfs] 백준 2606 코틀린 : 바이러스

dfs의 가장 기본적인 문제 2606번을 코틀린으로 풀어봤다.

 

아직 코틀린에 대해서 아주 익숙치가 않아서 알고리즘 문제를 푸는데 조금의 버벅거림은 있는듯 싶다.

 

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

2606번: 바이러스

 

풀이

우선 대표적인 탐색 문제였다.

 

선택사항에 따라서 bfs, dfs로 풀 수 있지만 나는 dfs를 더 선호해서 dfs로 풀었다. (물론 최소를 구하는 갯수에서는 bfs를 선호)

모든 인덱스를 돌게 되면서 방문하지 않았고 두 컴퓨터간의 연결이 되어있다면 dfs를 밟는 식으로 진행을 하였다.

 

dfs의 기초적으로 활용하는 문제로 dfs의 개념을 알게된다면 아주 편하게 사용을 했을것이다.

 

문제는 코틀린이 너무 익숙치 않다.. 

 

arr = Array(size){IntArray(size){init할 곳}}에 대해 익숙치 않고

사이즈를 메인문 안에서 받고 visited = BooleanArray(사이즈) 초기화하는거 잊지말자.

 

코드

package com.gyroh.algorithm


//연결되는 컴퓨터의 쌍 체크
var arr : Array<IntArray> = arrayOf()
// 방문 여부 체크
var visited : BooleanArray = booleanArrayOf()
var ans : Int = 0

fun main(){
    //컴퓨터 갯수
    var comcnt : Int = readLine()!!.toInt()
    // 연결 갯수
    var concnt : Int = readLine()!!.toInt()
    //c++처럼 memset + size를 받아온만큼 선언해준다고 보면됨.
    arr = Array(comcnt+1){IntArray(comcnt + 1){0}}
    visited = BooleanArray(comcnt + 1)

    for(i : Int in 0 until concnt){
        val line = readLine()!!.split(' ').map(String::toInt)
        arr[line[0]][line[1]] = 1
        arr[line[1]][line[0]] = 1

    }
    dfs(1)
    print(ans - 1) //1번이 감염된 상태에서 시작해서 전이 횟수니 - 1 출력
}

fun dfs(start : Int){
    ans++
    visited[start] = true

    for( i in 1 .. arr.lastIndex){
        if (!visited[i] && arr[start][i] == 1){
            dfs(i)
        }
    }
}