[ 알고리즘 / kotlin ] 백준 2573 빙산

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

이번 문제는 백준 2573 빙산 문제 입니다!!

 

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

2573번: 빙산

저는 BFS로 풀었어욥

 

먼저 문제를 간단하게 설명드리면 

 

요런 식으로 배열이 주어집니다. 빈칸은 0(물) 이고 그 외 숫자들은 빙산의 높이를 나타낸 것이에요

각각의 빙산들은 일년마다 상하좌우에 있는 물 개수(?) 즉, 0의 개수에 따라 낮아진다고 합니다

예를 들면 

저 초록색 4를 봅시다!!!

1년뒤에 저 4는 2가 되겠져 ? 왜냐 빨간색 체크부분을 보시면 4의 상하좌우 중 상 하의 위치에 물이 인접해있기 때문이죱

 

그러고 나서 빙산들이 두덩이 이상이 되었을 때 ( 한덩이는 상하좌우 인접해서 연결 돼 있는것을 뜻함니당)

몇년이 지났는지를 출력해주면 되0

 

( 설명을 잘 못하겠네여 ㅎ... 백준 설명 보시면 이해가 더 잘 되실수도,,,ㅠ)

 

 

그래서 저는 처음 접근을 할 때 아! 먼저 빙산들을 녹이고 bfs를 돌려야겠구나 라고 생각을 했어요ㅋ;

 

사실 이 문제 자체가 골드 5티어 문젠데 티어가 그리 높은 편은 아니지만 실버수준이라고 생각을 합니다 저는..!!

빙산을 녹이는 건 간단해유!

빙산들의 상하좌우를 탐색하며 0이 보일때마다 각 빙산의 높이를 1씩 줄여주면 되는거죠

 

아 그리고 각 배열의 값들은 0보다 낮아 질 수 없습니다요

제가 이 조건문을 빼놔서 -2827261라는 값도 볼 수 있었어요^^

 

그럼 녹이는 코드 먼저 볼게요

private fun melting(n: Int, m: Int) {
    vis = Array(n) { BooleanArray(m) }
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (arr[i][j] != 0) {
                for (k in 0 until 4) {
                    val curX = i + goX[k]
                    val curY = j + goY[k]
                    if (curX >= 0 && curX < n && curY >= 0 && curY < m && arr[curX][curY] == 0 && !vis[curX][curY]) {
                        if (arr[i][j] > 0) {
                            arr[i][j]--
                            vis[i][j]=true
                        }
                    }
                }
            }
        }
    }
}

돌면서 상하좌우를 탐색하고 방문했다는 표시를 해줬어요!

 

그 다음은 빙산의 덩이의 개수를 세는 코드에요 bfs를 이용했으여

 

private fun bfs(n: Int, m: Int) {
    vis = Array(n) { BooleanArray(m) }
    ice = 0
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (arr[i][j] != 0 && !vis[i][j]) {
                var queue: Queue<Pair<Int, Int>> = LinkedList()
                queue.add(Pair(i, j))
                ice++
                while (queue.isNotEmpty()) {
                    val x = queue.peek().first
                    val y = queue.peek().second
                    vis[x][y] = true
                    queue.poll()
                    for (k in 0 until 4) {
                        val curX = x + goX[k]
                        val curY = y + goY[k]
                        if (curX >= 0 && curX < n && curY >= 0 && curY < m && arr[curX][curY] != 0 && !vis[curX][curY]) {
                            queue.add(Pair(curX, curY))
                            vis[curX][curY] = true
                        }
                    }
                }
            }

        }
    }
}

bfs를 돌리며 한 덩이가 떼어질 때마다 ice를 증가 시켜주며 빙산 덩이의 개수를 세어줬으요

 

이상 주요 코드였습니다! 위 코드만 돌린다고해서 풀리진 않아요 자질구레한(?) 조건들이 있으니

아래 깃헙에서 전체 코드도 참고하시면 좋을것 같습니다.

https://github.com/Songgyubin/Algorithm/blob/master/baekjoon/BOJ_2573.kt

 

 

 

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!