[백준/Node.js] 2583번: 영역 구하기

문제 URL: https://www.acmicpc.net/problem/2583

 

직사각형들로 덮인 공간을 제외하고, 빈 영역이 몇 개나 되는지, 각 영역의 넓이는 얼마인지 구하는 문제입니다.

 

핵심 개념 정리

좌표 변환이 까다롭습니다. 문제에서 주는 수학 좌표계(왼쪽 아래가 원점)인데, 우리가 쓸 배열은 컴퓨터 좌표계(왼쪽 위가 원점)라서 y축을 뒤집어야 합니다. 이와 동시에 점으로 표현된 좌표들을 박스를 기준으로 변환하는 과정도 필요합니다.

 

BFS로 영역을 탐색합니다. 0인 칸들이 상하좌우로 연결된 덩어리를 찾아내면 됩니다.

 

JavaScript 특유의 함정들이 있습니다. 다른 언어 쓰다 온 사람들이 자주 헷갈리는 부분(저 포함ㅋ)들이 몇 가지 있어서, 이 글에서는 그런 부분들을 집중적으로 다뤄보겠습니다.

 

 

입력 처리

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [rowSize, colSize, boxNum] = input[0].split(' ').map(Number)
const matrix = Array.from({length: rowSize}, () => new Array(colSize).fill(0))
const boxes = input.slice(1).map(s => s.split(' ').map(Number))

여기서 주목할 건 Array.from() 메서드입니다. Python의 리스트 컴프리헨션 같은 게 JavaScript에는 없어서, 2차원 배열을 만들 때 이 메서드를 씁니다.

 

Array.from() 사용법

첫 번째 인자: 배열로 만들 대상. 여기서는 {length: rowSize}로 "길이만 rowSize인 유사 배열"을 만듭니다.
두 번째 인자: 각 요소를 어떻게 만들지 정하는 함수. () => new Array(colSize).fill(0)은 "colSize 길이의 배열을 0으로 채워라"는 뜻입니다.

// 이렇게 쓰면 안 됩니다!
const wrong = Array(rowSize).fill(Array(colSize).fill(0))
// 모든 행이 같은 배열을 참조해서, 한 칸만 바꿔도 한 열 전체가 바뀝니다.

// 이렇게 써야 합니다.
const correct = Array.from({length: rowSize}, () => new Array(colSize).fill(0))
// 각 행이 독립적인 배열이라 안전합니다.

 

 

좌표 변환

const fillBox = function(box) {
    const [x1, y1, x2, y2] = box
    const r1 = rowSize - y1 - 1  // 왼쪽 아래 y → 배열 row
    const r2 = rowSize - y2      // 오른쪽 위 y → 배열 row
    const c1 = x1                // x는 그대로 col
    const c2 = x2 - 1

    for (let r = r2; r <= r1; r++) {
        for (let c = c1; c <= c2; c++) {
            matrix[r][c] = 1
        }
    }
}

수학 좌표계에서 y가 클수록 위쪽인데, 배열에서는 row가 클수록 아래쪽입니다. 그래서 rowSize - y 로 뒤집어줍니다.

 

 

Queue 직접 구현하기

JavaScript 배열의 shift() 는 O(n)이라 느립니다. BFS처럼 큐를 많이 쓰는 알고리즘에서는 직접 구현한 큐가 훨씬 빠릅니다.

class Queue {
    constructor() {
        this.items = {}  // 객체로 구현
        this.head = 0    // 앞쪽 인덱스
        this.tail = 0    // 뒤쪽 인덱스
    }

    enqueue(item) {
        this.items[this.tail] = item
        this.tail++
    }

    dequeue() {
        const item = this.items[this.head]
        delete this.items[this.head]
        this.head++
        return item
    }

    get length() {
        return this.tail - this.head
    }
}

• 시간복잡도: enqueue와 dequeue 모두 O(1) 입니다. 배열의 shift()가 O(n)인 것과 비교하면 엄청난 차이죠.
• 구현 방식: 객체를 마치 배열처럼 쓰되, 인덱스를 직접 관리합니다. this.items[0], this.items[1] 이런 식으로 값을 넣고, 필요 없어지면 delete로 메모리를 정리합니다.

 

 

BFS 탐색

const bfs = function() {
    const queue = new Queue()
    const visited = Array.from({length: rowSize}, () => new Array(colSize).fill(false))
    const dr = [1, -1, 0, 0]
    const dc = [0, 0, 1, -1]
    const areas = []
    let count = 0
    
    for (let r = 0; r < rowSize; r++) {
        for (let c = 0; c < colSize; c++) {
            if (matrix[r][c] === 0 && !visited[r][c]) {
                visited[r][c] = true
                count += 1
                queue.enqueue([r, c])
                let area = 1

                while (queue.length) {  // 여기 주의!
                    const [row, col] = queue.dequeue()
                    for (let i = 0; i < 4; i++) {
                        const nr = row + dr[i]
                        const nc = col + dc[i]

                        if (0 <= nr && nr < rowSize && 0 <= nc && nc < colSize) {
                            if (matrix[nr][nc] === 0 && !visited[nr][nc]) {
                                queue.enqueue([nr, nc])
                                visited[nr][nc] = true
                                area += 1
                            }
                        }
                    }
                }
                areas.push(area)
            }
        }
    }
    areas.sort((a, b) => a - b)
    console.log(count)
    console.log(areas.join(' '))
}

 

 

 

while 조건문의 함정

Python이 주 언어인 사람들이 자주 하는 실수(나 포함ㅋ):

// Python 스타일 (JavaScript에서는 안 됩니다!)
while (queue) {  // 무한루프!
    // ...
}

JavaScript에서 배열이나 객체는 비어있어도 truthy입니다. 그래서 while (queue) 라고 쓰면 큐가 비어도 계속 돌아갑니다.

 

올바른 방법:

while (queue.length) {  // 큐에 원소가 있을 때만 실행
    // ...
}

 

 

---

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [rowSize, colSize, boxNum] = input[0].split(' ').map(Number)
const matrix = Array.from({length: rowSize}, () => new Array(colSize).fill(0))

// Queue 구현
class Queue {
    constructor() {
        this.items = {}
        this.head = 0
        this.tail = 0
    }
    enqueue(item) {
        this.items[this.tail] = item
        this.tail++
    }
    dequeue() {
        const item = this.items[this.head]
        delete this.items[this.head]
        this.head++
        return item
    }
    get length() {
        return this.tail - this.head
    }
}

// 박스 채우기 - 미리 다 파싱하지 않고 바로 처리
for (let i = 1; i <= boxNum; i++) {
    const [x1, y1, x2, y2] = input[i].split(' ').map(Number)
    const r1 = rowSize - y1 - 1
    const r2 = rowSize - y2
    
    for (let r = r2; r <= r1; r++) {
        for (let c = x1; c < x2; c++) {
            matrix[r][c] = 1
        }
    }
}

// BFS - visited 배열 없이 matrix 값으로 판단
const bfs = function() {
    const queue = new Queue()
    const dr = [1, -1, 0, 0]
    const dc = [0, 0, 1, -1]
    const areas = []
    let count = 0
    
    for (let r = 0; r < rowSize; r++) {
        for (let c = 0; c < colSize; c++) {
            if (matrix[r][c] === 0) {
                count++
                queue.enqueue([r, c])
                matrix[r][c] = 2  // visited 대신 matrix를 2로 변경
                let area = 1

                while (queue.length) {
                    const [row, col] = queue.dequeue()
                    for (let i = 0; i < 4; i++) {
                        const nr = row + dr[i]
                        const nc = col + dc[i]

                        if (nr >= 0 && nr < rowSize && nc >= 0 && nc < colSize) {
                            if (matrix[nr][nc] === 0) {
                                queue.enqueue([nr, nc])
                                matrix[nr][nc] = 2
                                area++
                            }
                        }
                    }
                }
                areas.push(area)
            }
        }
    }
    
    areas.sort((a, b) => a - b)
    console.log(count)
    console.log(areas.join(' '))
}

bfs()