[Swift] 백준_영역 구하기(2583)

문제

 

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

2583번: 영역 구하기

 

 

풀이

 

기본적인 BFS문제였다.

 

paper라는 변수를 만들고 주어진 입력을 받아 반복문을 통해 직사각형이 있는 곳을 1로 표시해주었다.(나머지는 0)

이후에 bfs를 돌리면되는데, paper[newX][newY]가 0인지만 확인해준뒤 맞다면 바로 큐에 넣어주었다.

 

while문 안에서 queue.removeFirst()를 할 때마다 이어져있는 넓이를 구하는 것이므로 area에 1을 더해주었고, while문을 탈출하게 되면 하나의 영역이 구해진 것이므로 result에 area를 추가해주었다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = input[0]
let n = input[1]
let k = input[2]
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var paper = Array(repeating: Array(repeating: 0, count: n), count: m)
var queue: [[Int]] = []
var count = 0
var result: [Int] = []
for _ in 0..<k {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    for i in input[1]..<input[3] {
        for j in input[0]..<input[2] {
            paper[i][j] = 1
        }
    }
}
for i in 0..<m {
    for j in 0..<n {
        if paper[i][j] == 0 {
            queue.append([i,j])
            paper[i][j] = 1
            count += 1
            var area = 0
            while !queue.isEmpty {
                area += 1
                let current = queue.removeFirst()
                for k in 0..<dx.count {
                    let newX = current[0] + dx[k]
                    let newY = current[1] + dy[k]
                    if newX < 0 || newY < 0 || newX >= m || newY >= n {
                        continue
                    }
                    if paper[newX][newY] == 0 {
                        paper[newX][newY] = 1
                        queue.append([newX,newY])
                    }
                }
            }
            result.append(area)
        }
    }
}
print(count)
print(result.sorted(by:<).map { String($0) }.joined(separator: " "))

 

 

_____________________________________________________________________________________________________

 

얼마전까지만해도 BFS가 아예 이해가 안갔는데 확실히 많이 풀어보니 조금씩 감이 잡히는 것 같다.