수영장 만들기.swift(백준 1113번)

문제 설명

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

1113번: 수영장 만들기

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.
16661
61116
16661
이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

 

풀이과정

풀이법을 떠올리는 것이 까다로운 문제였다.

일반적인 BFS 문제와 다르게 3차원으로 동작하기 때문이다.

 

생각1

우선 물을 채우고나서 세로로 빼는 것을 생각했다.

하지만 물이 빠지는 곳인지 아닌지 파악하는 것이 어렵기 때문에 다른 방법을 생각했다.

 

생각2

위의 방법 대신 떠올린 방법은 위에서부터 아래로 층마다 물을 빼주는 방식이다.

양옆의 물이나 벽의 높이를 체크하고 계속해서 물을 빼준다.

최종적으로 남은 물을 다 더해서 정답을 출력했다.

하지만 런타임 에러가 발생하며 실패했다.

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let N = input[0]
let M = input[1]

var pool: [[Int]] = []
var water: [[Int]] = []
var visited: [[Bool]] = []

var minLevel = 10
var maxLevel = 0

let direction = [(1,0), (0,1), (-1,0), (0,-1)]

for _ in 0..<N {
    let info = Array(readLine()!).map{ Int(String($0))! }
    minLevel = min(minLevel, info.min()!)
    maxLevel = max(maxLevel, info.max()!)
    
    pool.append(info)
}

func bfs(_ i: Int, _ j: Int, _ level: Int) {
    var queue: [(Int,Int)] = []
    var index = 0
    
    queue.append((i,j))

    visited[i][j] = true

    while index < queue.count {
        let (x,y) = queue[index]
        index += 1
        
        water[x][y] -= 1
        
        for (dx,dy) in direction {
            let nx = x + dx
            let ny = y + dy
            
            if visited[nx][ny] {
                continue
            }
            
            if nx <= 0 || ny <= 0 || nx >= N-1 || ny >= M-1 {
                continue
            }
            
            if (water[nx][ny] > 0) && ((pool[nx][ny] + water[nx][ny]) == level) {
                queue.append((nx,ny))
                visited[nx][ny] = true
            }
        }
    }
}

func flow(_ i: Int, _ j: Int, _ level: Int) {
    if !visited[i][j] {
        for (dx,dy) in direction {
            let nx = i + dx
            let ny = j + dy
            
            if (water[i][j]) > 0 && (pool[i][j] + water[i][j] > pool[nx][ny] + water[nx][ny]) {
                bfs(i, j, level)
                break
            }

        }
    }
}

var answer = 0
if N <= 1 || M <= 1 {
    answer = 0
} else {
    water = [[Int]](repeating: [Int](repeating: 0, count: M), count: N)

    // 벽을 제외한 모든 공간을 물로 채움
    for i in 1..<N-1 {
        for j in 1..<M-1 {
            water[i][j] = maxLevel - pool[i][j]
        }
    }

    for level in (minLevel+1...maxLevel).reversed() {
        visited = [[Bool]](repeating: [Bool](repeating: false, count: M), count: N)
        // 한 층씩 물을 비움
        for i in 1..<N-1 {
            for j in 1..<M-1 {
                flow(i, j, level)
            }
        }
    }
    
    water.forEach{ answer += $0.reduce(0, +) }
}

print(answer)

 

풀이 과정이 복잡해서 그랬을까...

구현 문제에서 막히기 시작하면 산으로 가기 때문에 아예 새로운 방법을 고민해보기로 했다.

 

생각3

위에서 생각했던 발상을 한번 꼬아서 생각해봤다.

위의 풀이 과정은 결국 "물"이 얼만큼 빠졌는지를 체크하는 형태로 진행했으니, 이번엔 "물" 대신 "벽"에 집중하기로 했다.

 

생각2를 구현하면서 생각했던건, 위(z축)에 위치한 물이 빠지는지 아닌지는 중요하지 않다는 점이다.

당연한 얘기겠지만, 기둥이 중간에 비여있는 경우는 없을테니까...

 

그래서 순서는 중요하지 않다고 생각해 아래에서 위로 계산했다.(물의 높이가 2에서 9까지)

물을 채울 수 있는지 여부만 체크했으며, 물의 깊이가 어떤지는 고려하지 않았다.(어차피 모든 층을 다 체크할테니)

 

다만 문제가 되는 상황은 가장자리이다.

가장자리와 맞닿은 부분의 물을 다 빼주어야 했기 때문이다.

가장자리 영역에서 방문할 수 있는 경우는 전부 물을 채울 수 없도록 해야했다. 

 

따라서, 가장자리 영역과 붙어있으며, 벽의 높이가 물의 높이보다 낮은 경우(물이 빠져야 하는 경우)에 대해선 check 변수를 활용해 구분시켰다. check가 false인 경우 값을 더해주지 않도록 해 가장자리 영역에 대한 예외처리를 할 수 있었다.

여기서 핵심은 불가능한 영역임에도 continue를 사용한 것인데, queue가 전부 비워지기 전까지 남아있는 지역을 전부 순회시켜야 했기 때문이다. 

 

queue는 구현하지 않고 queue의 특징만 활용했다.

(enqueue는 append, dequeue는 index접근)

index를 활용했으며, dequeue가 잦은 상황이라면 문제가 생길 수 있겠지만...

N과 M이 최대 50라 아무리 길어도 배열의 길이가 2500이라 괜찮았던 것 같다.

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let N = input[0]
let M = input[1]

var pool: [[Int]] = []
var visited: [[Bool]] = []

let direction = [(1,0), (0,1), (-1,0), (0,-1)]

var answer = 0

func bfs(_ x: Int, _ y: Int, _ level: Int) {
    var queue: [(Int,Int)] = []
    var index = 0

    queue.append((x,y))

    var check = true
    var cnt = 1

    visited[x][y] = true

    while index < queue.count {
        let (x,y) = queue[index]
        index += 1

        for (dx,dy) in direction {
            let nx = x + dx
            let ny = y + dy

            if nx < 0 || nx > N-1 || ny < 0 || ny > M-1 {
                check = false
                continue
            }

            if pool[nx][ny] < level && !visited[nx][ny] {
                visited[nx][ny] = true
                queue.append((nx,ny))
                cnt += 1
            }
        }
    }

    if check {
        answer += cnt
    }
}

for _ in 0..<N {
    pool.append(Array(readLine()!).map{ Int(String($0))! })
}

for water in 2...9 {
    visited = [[Bool]](repeating: [Bool](repeating: false, count: M), count: N)

    for i in 0..<N {
        for j in 0..<M {
            if pool[i][j] < water && !visited[i][j] {
                bfs(i, j, water)
            }
        }
    }
}

print(answer)

 

 

후기

생각2에서 시도한 방법도 틀린 방법이 아니라고 생각한다.

하지만 너무 복잡하다보니 예외 케이스를 찾지 못한 것 같다.(94%에서 런타임 에러 발생)

 

구현류의 문제에선 문제가 막히면 브레이크를 걸고 다시 풀어보는 연습이 중요할 것 같다.