[알고리즘] 코틀린 DFS(깊이우선탐색) 구현하기

DFS는 미로를 탐색할때 처럼 한방향으로 계속가다가 막히면 전 노드로 돌아와 다른방향으로 계속 가는것을 반복하는 탐색 방법이다.

재귀방식으로, 방문했거나 연결되지 않은 노드를 제외한 노드들을 계속 호출해줌으로써 구현할 수 있다.

 

www.acmicpc.net/problem/2606

2606번: 바이러스

▶ 코틀린으로 구현한 2606번 문제

 

import java.util.*

var n : Int = 0 // 컴퓨터의 수
var m : Int = 0 // 컴퓨터 쌍의 수

var graph = Array(101){Array(101){0} }
var visit = Array(101){0}

fun main(args:Array<String>) = with(Scanner(System.`in`)) {
    var a : Int
    var b : Int
    var sum = -1 // 감염된 컴퓨터 수 (본인도 포함이므로 -1부터 시작)

    n = nextInt()
    m = nextInt()

    for(i in 0 until m){
        a = nextInt()
        b = nextInt()

        graph[a][b] = 1
        graph[b][a] = 1
    }
    DFS(1)

    for(i in visit){
        sum += i
    } // 방문한 노드 다 더하기
    println(sum)
}

fun DFS(x : Int){
    visit[x] = 1
    for(i in 1..n){
        if(visit[i] == 1 || graph[x][i] == 0){
            continue
        }
        DFS(i)
    }
}