[백준/Swift] 2583 : 영역 구하기

문제  2583 : 영역 구하기

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

2583번: 영역 구하기

 

---

안녕하세요.

이번 문제는 dfs나 bfs 를 이용하면 쉽게 풀 수 있습니다.

• 문제 파악

그림에서

주어진 K개(위의 문제에선 K = 3)의 직사각형을 제외한 나머지 부분이 몇개의 영역으로 나누어지는지,

넓이는 몇인지 " 오름차순"으로 정렬 후 출력하는것이 문제입니다.

---

그림 좌표 크기를 담을 수 있는 2차원 배열(변수 : map)을 사용했습니다.

각 직사각형 구간을 for in 구문을 통해 방문해서 true 처리를 했습니다. 이제 빈 공간은 전부 false 입니다.

func drawRect(map : inout [[Bool]], rectList list : [rect]){
    for i in 0..<list.count{
        for y in list[i].start.y..<list[i].end.y{
            for x in list[i].start.x..<list[i].end.x{
                map[y][x] = true
            }
        }
    }
}

그 후에 

완전 탐색을 실행하며 0,0 부터 7,5까지 탐색을 하면서 map에 false처리된 곳이 있다면, bfs탐색을 통해 true 처리를 하고, 노드 방문 횟수를 측정했습니다.

 

추가로 저는 좌표들을 저장할 rect 클래스를 구현했습니다.

class rect{
    var start : coord
    var end   : coord
    init(x1: Int,y1 : Int, x2 : Int, y2 : Int){
        start = coord(x: x1, y: y1)
        end   = coord(x: x2, y: y2)
    }
}
class coord{
    var x : Int
    var y : Int
    init(x : Int, y : Int){
        self.x = x
        self.y = y
    }
}

rect에는 시작점을 저장할 수 있는 start 맴버 변수, 끝점을 저장하는 end 맴버 변수를 구현했습니다.

---

다음은 코드입니다.

import Foundation
//직사각형 저장할 클래스
class rect{
    var start : coord
    var end   : coord
    init(x1: Int,y1 : Int, x2 : Int, y2 : Int){
        start = coord(x: x1, y: y1)
        end   = coord(x: x2, y: y2)
    }
}
class coord{
    var x : Int
    var y : Int
    init(x : Int, y : Int){
        self.x = x
        self.y = y
    }
}
// map안에 직사각형을 그려주는 함수
func drawRect(map : inout [[Bool]], rectList list : [rect]){
    for i in 0..<list.count{
        for y in list[i].start.y..<list[i].end.y{
            for x in list[i].start.x..<list[i].end.x{
                map[y][x] = true
            }
        }
    }
}

func edgeCheck(nx: Int, ny : Int,height : Int, width : Int) -> Bool{
    if nx < 0 || nx > width - 1 || ny < 0 || ny > height - 1 {
        return true
    }
    return false
}
//bfs탐색
func bfs(x : Int, y : Int , width: Int, height : Int, result : inout [Int], map : inout [[Bool]]){
    var count     = 1
    var queue     = [(x,y)]
    var index     = 0
    let direction = [(-1,0),(1,0),(0,1),(0,-1)]
    
    while queue.count != index {
        let (curX,curY) = queue[index]
        for (dx,dy) in direction{
            let (nx,ny) = (curX + dx, curY + dy)
            if edgeCheck(nx: nx, ny: ny, height: height, width: width) { continue }
            if map[ny][nx] == false {
                map[ny][nx] = true
                count += 1
                queue.append((nx,ny))
            }
        }
        index += 1
    }
    result.append(count)
}
/**
 * @param : rectList = 직사각형의 시작, 끝 좌표를 저장할 배열
 * @param : section = 남은 구역이 몇개 있는지?
 * @param : result = bfs탐색후 결과 저장.
 */
func BOJ_2583(){
    let hwk      = readLine()!.split(separator: " ").map{Int(String($0))!}
    let height   = hwk[0]
    let width    = hwk[1]
    let n        = hwk[2]
    var map      = Array(repeating: Array(repeating: false, count: width + 1), count: height + 1)
    var rectList = [rect]()
    var section  = 0
    var result   = [Int]()
    
    for i in 0..<n{
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        rectList.append(rect(x1: input[0], y1: input[1], x2: input[2], y2: input[3]))
    }
    
    drawRect(map: &map, rectList: rectList)
    
    for y in 0..<height{
        for x in 0..<width{
            if map[y][x] == false {
                section += 1
                map[y][x] = true
                bfs(x: x, y: y, width: width, height: height, result: &result, map: &map)
            }
        }
    }
    print(section)
    print(result.sorted().map{String($0)}.joined(separator: " "))
    
}

BOJ_2583()