[백준/Swift] 2573 : 빙산

여러분 안녕하세요~~

이번 문제는 dfs/bfs 문제 2573 : 빙산 입니다.

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

2573번: 빙산

---

한탄하는중,, 괄호 스킵하셔도 됩니다.

(하.. 이 문제를 제가 .. 이전에 토마토 https://www.acmicpc.net/problem/7576  이 문제를 풀었던 기억이 갑자기 떠오르면서 비슷한 문제인가? 

문제를 제데로 파악 하지 않고 그림1 과 그림 2를 보고,, 토마토 문제처럼 한 해가 지날 때마다 모든 빙하가 -1씩 감소되는 문제인줄 알고 계속 풀었었습니다...

근데 이 입력값도 함정이었던게,, 결과가 2로 출력이 돼서 제 코드가 정말 맞는 코드 인 줄 알고 몇번을 시도했었는데.. 도저히 안되서,

마음을 다잡고 다시 문제를 봤는데 제가 문제를 잘못 봤었다는 사실이.._이제부터 백준 문제 무조건 4번씩은 보고 문제 풀려구요..)

---

간단하게 문제 파악하면서 시작하겠습니다!!

 

북극의 바다에 빙산이 있는데, 녹고있다...

1년마다 빙산의 높이가 줄어드는데, 높이가 0 이하로 감소하지는 않는다.

또한 상하좌우 네 방향 중 바다 '0' 인 부분이 있을 경우 인접한 바다 갯수만큼 해당 빙산의 높이는 줄어든다.

 

빙산이 두 덩이가 될 경우에 그 특정 기간(년도)를 출력하거나,

또는 빙산이 두 덩이 이상이 되지 않고 한 덩이인 채 다 녹을 경우에는 0으로 출력을 하면 됩니다.

빙산 높이 2를 보게된다면, 1년이 지난 후에는 좌, 위 의 인접 구간이 0 이기 때문에, 높이가 2였던 빙산은 0이 됩니다.

4 또한 마찬가지입니다. 인접한<상, 하>가 0이기 때문에 2가 줄어들어서 높이는 2가 됩니다.

(저는 다 1씩 줄어든 줄 알고 풀었었,,)

1년이 지난 후 그림2가 되고, 2년이 지난 후에야 비로소 3덩이가 되어 결과를 출력하게 됩니다.

---

이때 주의해야할 점이 있습니다.

맨 처음 사진의 (5,3)좌표 (값 = 5) 를 보게 된다면, 해당 빙산을 기준으로 인접한 상하좌우는 바다가 아닌 빙산으로 둘러싸여 있습니다. 이럴 경우 빙산은 녹지 않습니다!!!!!

또한 문제를 풀다보면 빙산은 모두 동시에 녹습니다. 예를들어 맵을 순차적으로 탐색 할 경우, 그림1 기준(year == 0일 때) map[1][1]부터 순차 탐색을 하는데, 이때 map[1][1] == 2인데, 위, 왼쪽이 0이므로 2-2 == 0이 됩니다. 근데 map[1][1]이 녹은 후에 바로 그 오른쪽 칸을 탐색할 경우 원래 4에서 3이 되어야 하는데, 4에서 2가 되도록 코드를 짤 경우 오답이 됩니다!! 주의하세요

뭐가 정답일까요?

.

..

...

 case1이 정답입니다. 빙산이 녹는 경우는 모든 빙산이 한번에 녹아야합니다. 근데 dfs나 bfs탐색을 할 때 상하좌우 탐색을 4번 진행 할 경우, 이미 탐색했던 이전에 녹는것이 현재 진행중이었던 빙하가 0이 되기 전에 그 다음 빙하도 동시에 녹아야하는데, (case2) 처럼 진행 되도록 코드가 구성될  수 있습니다.

 저는 이 경우를 맵과 동일한 크기의 visited 2*2배열을 만들어 이미 방문했다면 true 처리를 한 후 false일 때, 즉 방문하지 않고, "0"인 바다에 한 해서만 빙산을 녹도록 했습니다. 

(문제만 제대로 파악했다면 바로 정답인데,,문제를잘못봐서 6번이나 토마토 dfs문제처럼 풀었다는게 사실..)

 

그림 2 -> 3이 되도록 문제를 구성한다면 결과는 맞지 않을까 생각합니다.

---

저의 코드에서 핵심은 dfs입니다.

다른 2개의 함수가 있지만 탐색과 녹는작업을 실행하라고만 하는 함수이고, 실질적으론 dfs를 통해 모든 것을 처리했습니다.

이때 dfs를 구현할 때 처음에 stack을 사용한 while문을 구성했는데, 이 방법보단 dfs 함수 재귀가 더 편하고 빠르게 구현될 것 같아 재귀함수로 처리했고,

 

가장 중요한 동시에 빙하가 녹는 조건을 추가했습니다.

//빙하가 동시에 녹기위한 조건! 탐색안한 구간에 대해 notIce를 증가시킨다.
            if visit[ny][nx] == false{
                notIce += 1
            }

---

다음은 제 코드입니다.

 

import Foundation

/**
 *HW 지도의 HW[0]높이, HW[1]넓이 저장
 *isVisited : dfs탐색을 통해 이미 빙산을 탐색했을 경우 true처리
 */
var HW = readLine()!.split(separator:" ").map{Int(String($0))!}
var direction = [(-1,0),(1,0),(0,-1),(0,1)]
var sea = Array(repeating: [Int](), count: HW[0])
var year = 0
for y in 0..<HW[0]{
    sea[y] = readLine()!.split(separator:" ").map{
        Int(String($0))!
    }
}

/**
 * Entry potint <시작점>
 * 빙하가 다 녹을 때 ( 0을 반환할 때까지 ) while문 종료
 * or 그 이전에 빙하가 녹아 특정 년도에 빙하가 2개 이상이 있을 경우 while문 종료
 * 이 두가지 조건중 한개로 무조건 while문은 끝나게 되어 있습니다.
 * ---------------------------------------------------
 * @param : isAllIceBergMelted = 모든 빙산이 녹았는가? 어떻게 확인하지?
 * ==> 빙하가 두개가 있는지 탐색하는 함수 detected(visited:allIceBergMelted:)에서 dfs탐색이 아예 없을 경우 빙하가 다 녹았음을 뜻한다
 *     이 경우 while문 종료
 * @param : isVisited1 = detected함수에서 빙산이 녹았는지 탐색할 때 방문한 빙산을 표시하기 위한 변수
 * @param: isVisited2 = meltIngberg(visited:) 인접한 바다 개수에 따라 빙산을 녹는 작업을 진행 할 때 빙산이 녹았는지 탐색할 때 방문한 빙산을 표시하기 위한 변수
 * // 혹시 isVisited2 = isVisited1로하면 inout에서 메모리 관련 이상한 점이 발생할까봐 그냥 추가로 변수를 할당했습니다.
 * @param : isSeparated = 빙하 탐색을 통해 빙하가 녹아 2개 이상의 구역이 발생했는가? 했으면 true else false
 * 발생했다면, 빙하가 만약 isAllIceBergMelted == true? -> 0 출력
 * 아닐 경우 2개 이상의 빙하지역 발생! break 후 특정 년도 출력
 */
while( true ) {
    var isAllIceBergMelted = false
    var isVisited1 : [[Bool]] = Array(repeating: Array(repeating: false, count: HW[1]), count: HW[0])
    var isVisited2 = isVisited1
    //2개의 구역이 있는가?!
    let isSeparated : Bool = detected(visited: &isVisited1, allIceBergMelted : &isAllIceBergMelted)
    
    if !isSeparated{
        meltIceberg(visited : &isVisited2)
    }else{
        //두개 구역 분리되면 종료 또는 빙하가 자연스래 녹을 경우 0 출력
        if isAllIceBergMelted {
            year = 0
            break
        }else{
            break
            
        }
    }
    year += 1
}
//결과 출력
print(year)
/*
 ----------------------------------------------------------------
 * 여기서부터는 while문에 쓰이는 함수들이 정의되어 있습니다.
 * detected(visited:allIceBergMelted) : 빙하 2개 이상있는지 탐색하는 함수
 * meltIceberg(visited:) 빙하가 녹는 작업 실시!
 * dfs(paramX:paramY:isMelt:visit:) isMelt의 true false여부에 따라 빙하가 녹는작업? or 그냥 빙하가 2개인 구간 detected 탐색 할지 결정됨! - 재귀 사용
 */

//땅이 2개인가? 탐색하는 함수
// 2개이상의 dfs 실행될 경우 true 반환 후 while문 종료, 아니면 meltIceberg()탐사 후 while문 반복
func detected(visited: inout [[Bool]] ,allIceBergMelted iceBerg : inout Bool) -> Bool{
    var dfsTry = 0
    for y in 0..<HW[0]{
        for x in 0..<HW[1]{
            //여기서 방문하지 않은 땅이라면 방문하고 dfs에서 true처리 근데, 만약 땅이 2개라면 dfs 두번 실행되겠지?! 호호,,
            if sea[y][x] != 0 && visited[y][x] == false{
                dfs(paramX: x, paramY: y,isMelt: false,visit: &visited)
                dfsTry += 1
                if dfsTry == 2 {
                    return true
                }
            }
        }
    }
    
    //만약 while도중 빙하가 모두 녹아버렸다면 dfs작업 안 한거니까 return true 후 while문 종료
    if dfsTry == 0 {
        iceBerg = true
        return true
    }
    return false
}

//빙하가 녹아 샤르르~
func meltIceberg(visited: inout [[Bool]]){
    for y in 0..<HW[0]{
        for x in 0..<HW[1]{
            if sea[y][x] != 0{
                dfs(paramX: x, paramY: y,isMelt: true, visit: &visited)
                //빙하는 한 구역밖에 없을 테니 reutrn실시!!
                return
            }
        }
    }
}
/**
 * @param : notIce = 빙하가 아닌 값, 즉 바다인 경우를 세는 변수다.
 * ismalt true면 dfs를 통해 한개의 빙산이 한칸씩 녹음, false면 그냥 탐색만 (2개 dfs되면 2개이상빙하)
 * 맨 처음에 stack을 사용한 dfs를 구현했었는데, 이 경우 약간 구현하기 귀찮? 어려워보여서 재귀 호출로 dfs를 수행하며 해결했다.
 */
func dfs(paramX x :Int,paramY y :Int,isMelt : Bool, visit : inout [[Bool]]){
    var notIce = 0
    visit[y][x] = true
    notIce = 0
    for (dx,dy) in direction{
        let nx = dx + x
        let ny = dy + y
        if nx < 0 || nx > HW[1] - 1 || ny < 0 || ny > HW[0] - 1{
            continue
        }
        if sea[ny][nx] == 0 && isMelt{
            //빙하가 동시에 녹기위한 조건! 탐색안한 구간에 대해 notIce를 증가시킨다.
            if visit[ny][nx] == false{
                notIce += 1
            }
            
        }
        //만약 방문하지 않은 빙하이면!!!!!!
        if sea[ny][nx] != 0 && visit[ny][nx] == false{
            visit[ny][nx] = true
            dfs(paramX: nx, paramY: ny, isMelt: isMelt, visit: &visit)
                
        }
    }
    // 위의 포문 (상하좌우) 탐색을 통해 바다인 칸 (notIce)만큼 빼준다.
    if isMelt{
        sea[y][x] -= notIce
        if sea[y][x] < 0 {
            sea[y][x] = 0
        }
    }

}

 

코드가 길고 난해하지만,.., 도움이 되실.,,분들이 있다면,, 

긴 글 읽어주셔서 감사합니다!!