[백준 2146] - 다리만들기(Kotlin)[골드3]

문제

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

2146번: 다리 만들기

문제 풀이

대륙간의 연결하는데 필요한 최소한의 비용으로 다리를 건설하는 것이 목표이다.

그렇다면 첫 번째로 대륙을 구별해야 할 것이다.

A대륙에서 B대륙으로 다리를 놓기 위해서는 A대륙과 B대륙을 구별해줘야 한다.

다음과 같이 대륙을 구별해 줬다.

어떻게 구별했냐??

배열이 1인 경우 bfs를 진행하고, 땅을 밟는 경우 라벨링을 해줬다.

그러다가 bfs가 중지되면 라벨을 +1 하고, 다시 땅을 만날 경우 bfs를 진행하고 라벨링을 해줬다.

그 결과 아래와 같은 결과가 나오게 된다.

 

그렇다면 대륙간의 연결은 어떻게 해야 할까?

이걸 고민하기 이전에 어디서부터 연결을 시작할까에 대해서 고민해야 한다.

보통은 땅의 모서리에서 다른 땅의 모서리로 연결하는 게 최소한의 거리일 것이다라고 판단했다.

그렇다면 땅의 모서리를 어떻게 판단할까?

나는 바다와 한 면이라도 인접한 경우 모서리라고 판단했다.

그렇다면 그 모서리에서 이제 자신의 대륙이 아니고 바다만을 건너다가 다른 대륙을 만날 경우 그때의 길이를 구했고

최솟값을 구하면 될 것이다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min
var size = 0
val q : Queue<Pair<Int, Int>> = LinkedList()
val edgeQ : Queue<Pair<Int,Int>> = LinkedList()
val x = arrayOf(1,-1,0,0)
val y = arrayOf(0,0,1,-1)
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    size = br.readLine().toInt()
    val graph = Array(size) { Array(size, { 0 }) }
    var visit = Array(size,{ Array(size,{false} )})
    var cnt =1
    for(i in 0 until size){
        val token = br.readLine().split(" ")
        for(j in 0 until size){
            graph[i][j]=token[j].toInt()
        }
    }
    for(i in 0 until size){
        for(j in 0 until size){
            if(graph[i][j]==1 && !visit[i][j]) {
                island(graph, visit, Pair(i, j), cnt)
                cnt++
            }
        }
    }
    print(connection(graph))
}
fun island(ary : Array<Array<Int>>,visit : Array<Array<Boolean>>,loc : Pair<Int,Int>,cnt : Int){ //라벨링
    q.add(loc)
    while(!q.isEmpty()){
        val now = q.poll()
        if(visit[now.first][now.second])
            continue
        visit[now.first][now.second]=true
        ary[now.first][now.second]=cnt
        var check = false
        for(i in 0 until 4){
            val mx = now.first +x[i]
            val my = now.second+y[i]
            if(mx!in ary.indices || my!in ary.indices) //배열 범위가 아닌 경우
                continue
            if(visit[mx][my]) //방문처리.
                continue
            if(ary[mx][my]==0) {//바다 일 경우
                check = true
                continue
            }
            q.add(Pair(mx,my))
        }
        if(check) //한면이라도 바다와 인접한 경우
            edgeQ.add(now)
    }
}
fun connection(ary : Array<Array<Int>>) : Int{ //다리 연결
    val tempQ : Queue<Pair<Pair<Int,Int>,Int>> = LinkedList()
    var answer = 100000
    while(!edgeQ.isEmpty()){
        tempQ.add(Pair(edgeQ.poll(),0))
        val marker = ary[tempQ.peek().first.first][tempQ.peek().first.second] //현재 대륙의 라벨 값
        var visit = Array(size,{ Array(size,{false} )})
        while(!tempQ.isEmpty()){
            val now = tempQ.poll()
            if(visit[now.first.first][now.first.second])
                continue
            visit[now.first.first][now.first.second]=true
            for(i in 0 until 4){
                val mx = now.first.first+x[i]
                val my = now.first.second+y[i]
                if(mx !in ary.indices || my!in ary.indices) //배열 범위이 아닌 경우
                    continue
                if(visit[mx][my]) //방문한 경우
                    continue
                if(ary[mx][my]==marker) //같은 대륙일 경우
                    continue
                if(ary[mx][my]!=0) { //다른대륙이고 바다가 아닌 경우
                    answer = min(answer, now.second + 1)
                    continue
                }
                tempQ.add(Pair(Pair(mx,my),now.second+1))
            }
        }
    }
    return answer-1
}

 

회고

• 지금 와서 생각해 보니 굳이 visit 배열을 생성해서 방문처리를 하지 않고, 라벨링값과 다른 것을 이용해서 방문처리를 했으면 메모리와 시간적으로 훨씬 절약할 수 있을 거 같다.
• indices라는 기능을 처음 알았는데 배열의 유효범위인지 판단할 수 있어서 정말 유용한 거 같다.