BOJ: #2583 - 영역 구하기

주어지는 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점의 값을 배열의 인덱스로 치환하는 과정을 바로 생각하기가 어려워서 손으로 열심히 계산하면서 풀었다. 이 과정 이후에는 탐색 문제와 동일하게 풀면 된다. 각 영역의 넓이는 visited의 크기를 반환하면 되는데, 이 때 왜인지는 모르겠지만 중복값이 들어가서 크기가 맞지 않아 visited를 Set으로 선언하여 중복값 처리를 해줬다.

 

문제

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

 

내가 작성한 코드

Swift

let n = readLine()!.split(separator: " ").map { Int(String($0))! }
var board = Array(repeating: Array(repeating: 0, count: n[1]), count: n[0])

for _ in 0..<n[2] {
    let area = readLine()!.split(separator: " ").map { Int(String($0))! }
    let startX = n[0] - area[1] - 1
    let startY = area[0]
    let endX = n[0] - area[3]
    let endY = area[2] - 1

    for i in endX...startX {
        for j in startY...endY {
            board[i][j] = 1
        }
    }
}

var area = [Int]()
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]
var count = 0
for i in 0..<n[0] {
    for j in 0..<n[1] {
        if board[i][j] == 0 {
            var visited = Set<[Int]>()
            visited.insert([i, j])
            var queue = [[i, j]]
            while !queue.isEmpty {
                let v = queue.removeFirst()
                for (x, y) in zip(dx, dy) {
                    let nx = x + v[0]
                    let ny = y + v[1]
                    if nx < 0 || nx >= n[0] || ny < 0 || ny >= n[1] || board[nx][ny] == 1 {
                        continue
                    }
                    if board[nx][ny] == 0 {
                        visited.insert([nx, ny])
                        queue.append([nx, ny])
                        board[nx][ny] = 1
                    }
                }
            }
            area.append(visited.count)
            count += 1
        }
    }
}

print(count)
print(area.sorted().map({ String($0) }).joined(separator: " "))