[알고리즘] 코틀린 BFS(너비우선탐색) 의 level 구하기

BFS는 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

코드로 구현할 때에는 큐를 이용해서 구현하는데, 시작점을 큐에 삽입하고, 큐를 반환하면서 다음 레벨의 모든 노드를 검사하여 연결된 모든 노드들을 큐에 삽입하며 전부 탐색하는 방식으로 구현한다.

여기서 레벨을 알아내려면,

BFS의 반복문에 현재 들어와있는 큐의 개수만큼만 반복하게 하는 조건을 하나 더 달아주고 카운트하면,

원하는 노드의 레벨을 알 수 있다.

시작점과 그 노드의 레벨은 곧 그 두 점 사이의 거리를 뜻한다.

 

응용하는 문제로

www.acmicpc.net/problem/2644

2644번: 촌수계산

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

import java.util.*

var n = 0 // 사람의 개수
var a = 0 // 서로 다른 두 사람
var b = 0 // 서로 다른 두 사람
var m = 0 // 관계의 개수
var count = 0 // 촌수
lateinit var q : Queue<Int>

var graph = Array(101) {Array<Int>(101) {0}} // 관계 2차원 배열로 표현
var visit = Array(101){0} // 방문 여부 표시

fun main(args: Array<String>) = with(Scanner(System.`in`)) {
    n = nextInt()
    a = nextInt()
    b = nextInt()
    m = nextInt()
    q = LinkedList()

    for (i in 0 until m) {
        var j = nextInt()
        var q = nextInt()
        graph[j][q] = 1
        graph[q][j] = 1
    } // 관계 표시해줌

    BFS(a)
}

fun BFS(x : Int){
    var tmp = x
    q.add(tmp) // 자기자신 큐에 삽입
    visit[tmp] = 1;

    while(!q.isEmpty()){
        for(i in 1..q.size){
            tmp = q.poll()

            if (b == tmp) {
                return println(count)
            } // 관계를 찾는 상대방을 마주치게 되면, 종료

            for(j in 1..n){
                if(visit[j] == 0 && graph[tmp][j] == 1) {
                    q.add(j)
                    visit[j] = 1
                } // 방문하지 않았고, 연결되있다면 큐에 삽입, 방문 처리
            }
        }
        count++ // bfs 레벨파악을 위해 q의 사이즈만큼 반복하여 종료될 때 마다 count
    }
    println(-1) // 관계가 성립되지 않음
}