[백준] 17472번: 다리 만들기 2 - Kotlin[코틀린]

2023. 11. 24. 21:40·알고리즘/Baekjoon

문제

 

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

 


풀이

 

 이 문제의 풀이 과정과 사용한 알고리즘은 다음과 같다.

 

 1. 섬에 고유 번호 부여 (DFS): 입력받은 지도를 DFS나 BFS를 이용하여 각 섬에 번호를 부여해준다. 입력에서 1이 섬이기 때문에 첫번째 섬부터 2번으로 부여해주었다.

 

 2. 각 섬을 연결할 수 있는 방법 구하기 (BFS): 각 섬을 연결하는 가능한 모든 다리를 찾아준다. 길이가 1보다 큰 다리들을 거리에 따라 오름차순으로 정렬될 수 있게 우선 순위 큐에 저장한다.

 

 3. 최소 신장 트리(MST) 구하기 (크루스칼): 우선 순위 큐에 저장된 다리 정보를 활용하여 크루스칼 알고리즘을 수행한다. MST를 구하고 이를 통해 최소 비용을 계산한다.

 

 최종적으로 구한 MST가 올바르게 형성되었다면 최소 비용을 출력하고, 그렇지 않다면 -1을 출력한다.

 


코드

 

import java.util.*

data class Point(val x: Int, val y : Int, val value: Int)
data class Edge(val start: Int, val end: Int, val value: Int) : Comparable<Edge> {
    override fun compareTo(other: Edge): Int = value.compareTo(other.value)
}

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

    val st = StringTokenizer(br.readLine())
    val rows = st.nextToken().toInt()
    val cols = st.nextToken().toInt()

    val map = Array(rows){ IntArray(cols) }
    repeat(rows) { i ->
        StringTokenizer(br.readLine()).run {
            repeat(cols) { j ->
                map[i][j] = nextToken().toInt()
            }
        }
    }

    // 탐색 가능 범위
    val dx = arrayOf(-1, 0, 1, 0)
    val dy = arrayOf(0, 1, 0, -1)
    fun isRange(nx: Int, ny: Int) = nx in 0 until rows && ny in 0 until cols

    // 섬 번호 붙이기
    fun dfs(x: Int, y: Int, idx: Int) {
        map[x][y] = idx
        for(i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            if (isRange(nx, ny) && map[nx][ny] == 1) {
                dfs(nx, ny, idx)
            }
        }
    }

    var island = 2
    repeat(rows) { i ->
        repeat(cols) { j ->
            if (map[i][j] == 1) {
                dfs(i, j, island++)
            }
        }
    }

	// 다리 정보 저장을 위한 우선순위 큐
    val pq = PriorityQueue<Edge>()

    // 경로 만들기
    fun makeBridge(x: Int, y: Int, idx: Int) {
        for(i in 0 until 4) {
            val queue : Queue<Point> = LinkedList()
            queue.add(Point(x, y, 0))

            while(queue.isNotEmpty()) {
                val tmp = queue.poll()
                val nx = tmp.x + dx[i]
                val ny = tmp.y + dy[i]

                if(isRange(nx, ny)) {
                    if(map[nx][ny] == idx) continue
                    if(map[nx][ny]==0) {
                        queue.add(Point(nx, ny, tmp.value + 1))
                    } else {
                        if(tmp.value > 1) {
                            pq.add(Edge(idx, map[nx][ny], tmp.value))
                        }
                    }
                }
            }
        }
    }

	// 모든 섬에 대해 다리 정보 생성
    repeat(rows) { i ->
        repeat(cols) { j ->
            if (map[i][j] != 0) {
                makeBridge(i, j, map[i][j])
            }
        }
    }

	// 크루스칼 알고리즘을 위한 유니온-파인드
    val parent = IntArray(island){ it }
    fun find(a: Int) : Int {
        if (parent[a] != a) {
            parent[a] = find(parent[a])
        }
        return parent[a]
    }
    fun union(a: Int, b: Int) {
        val x = find(a)
        val y = find(b)
        if(x<y) {
            parent[y] = x
        } else {
            parent[x] = y
        }
    }
    
    // 크루스칼 알고리즘으로 MST 구하기
    fun kruskal(): Int {
        var sum = 0

        while(pq.isNotEmpty()) {
            val edge = pq.poll()
            if(find(edge.start)!=find(edge.end)) {
                sum += edge.value
                union(edge.start, edge.end)
            }
        }
        
        // 모든 섬이 연결되어 있는지 확인
        for(i in 2 until island) {
            if(find(parent[i])!=2) {
                sum = -1
            }
        }

        return sum
    }

    bw.write("${kruskal()}")
    bw.flush()
    bw.close()
    br.close()
}

 

'알고리즘 > Baekjoon' 카테고리의 다른 글

[백준] 2529번: 부등호 - Kotlin[코틀린]  (0) 2023.11.29
[백준] 18352번: 특정 거리의 도시 찾기 - Kotlin[코틀린]  (0) 2023.11.28
[백준] 6479번: 전력난 - Kotlin[코틀린]  (0) 2023.11.22
[백준] 1774번: 우주신과의 교감 - Kotlin[코틀린]  (0) 2023.11.20
[백준] 4386번: 별자리 만들기 - Kotlin[코틀린]  (0) 2023.11.14
'알고리즘/Baekjoon' 카테고리의 다른 글
  • [백준] 2529번: 부등호 - Kotlin[코틀린]
  • [백준] 18352번: 특정 거리의 도시 찾기 - Kotlin[코틀린]
  • [백준] 6479번: 전력난 - Kotlin[코틀린]
  • [백준] 1774번: 우주신과의 교감 - Kotlin[코틀린]
junghoooooon
junghoooooon
  • junghoooooon
    코드팁스
    junghoooooon
  • 전체
    오늘
    어제
    • 전체 (120)
      • 안드로이드 (0)
        • 코드팁스 (0)
      • 유니티 (0)
        • 코드팁스 (0)
      • 알고리즘 (118)
        • 알고리즘 (0)
        • Baekjoon (118)
      • GitHub (0)
      • 티스토리 (2)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      이분 탐색
      우선순위 큐
      소수 판정
      수학
      백트래킹
      BFS
      유니온파인드
      큐
      그래프 탐색
      투 포인터
      정렬
      에라토스테네스의 체
      MST
      그래프이론
      분리집합
      누적 합
      브루트포스
      크루스칼
      그리디
      dfs
      모듈러 곱셈 역원
      구현
      재귀
      프림
      스택
      피보나치
      분할 정복
      티스토리
      DP
      문자열
    • hELLO· Designed By정상우.v4.10.2
    junghoooooon
    [백준] 17472번: 다리 만들기 2 - Kotlin[코틀린]
    상단으로

    티스토리툴바