[BOJ] 5547 - 일루미네이션 (Python, JavaScript)

 

 

아이디어

 

BFS로 건물 내부와 외부를 구분한 후, 외부에 보이는 벽면의 수를 구한다.

 

 

풀이 #1 (Python)

 

문제의 정육각형 좌표 값 y가 홀수일 때를(인덱스 기준 짝수) 기준으로 위치 변화 값들을 튜플로 리스트 delta에 저장한다.

 

지도의 너비 W, 지도의 높이 H를 입력 받고, 집의 건물 배치를 2차원 리스트 buildings에 저장한다.

지도 가장자리 부분의 좌표들을 인자로 함수 bfs를 호출하여 건물 내부와 외부를 구분한다.

인덱스가 홀수인 행이면서 행의 위치가 변하면 delta에서 열 변화 값을 1을 감소시켜 위치 변화 값을 조정한다.

함수 bfs 호출로 지도 buildings에서 외부 공간은 -1, 내부 공간에서 건물이 있는 곳은 1, 없는 곳은 0의 값을 갖게 된다.

 

이후 건물이 있는 좌표들을 인자로 함수 count를 호출하여 외부에서 보이는 벽면의 수를 구해 결과값 res에 저장한다.

함수 count에서는 주변 칸들이 지도 범위를 벗어나거나 외부와 닿아 있으면 벽면의 수 cnt를 1 증가시키고, cnt를 반환한다.

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)]

def bfs(r, c):
    queue = [(r, c)]
    while queue:
        r, c = queue.pop(0)
        for dr, dc in delta:
            if r%2 and dr:
                nr, nc = r+dr, c+dc-1
            else:
                nr, nc = r+dr, c+dc
            if H > nr >= 0 and W > nc >= 0:
                if buildings[nr][nc] == 0:
                    buildings[nr][nc] = -1
                    queue.append((nr, nc))

def count(r, c):
    cnt = 0
    for dr, dc in delta:
        if r%2 and dr:
            nr, nc = r+dr, c+dc-1
        else:
            nr, nc = r+dr, c+dc
        if H > nr >= 0 and W > nc >= 0:
            if buildings[nr][nc] < 0:
                cnt += 1
        else:
            cnt += 1
    return cnt

W, H = map(int, input().split())
buildings = [list(map(int, input().split())) for _ in range(H)]
for r in [0, H-1]:
    for c in range(W):
        if buildings[r][c] == 0:
            buildings[r][c] = -1
            bfs(r, c)
for c in [0, W-1]:
    for r in range(H):
        if buildings[r][c] == 0:
            buildings[r][c] = -1
            bfs(r, c)
res = 0
for r in range(H):
    for c in range(W):
        if buildings[r][c] == 1:
            res += count(r, c)
print(res)

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작한다.

 

함수 bfs에서 주변 칸의 좌표 값 nr, nc를 먼저 인덱스가 짝수인 행을 기준으로 할당한 후,

인덱스가 홀수인 행이면서 행의 위치가 변하면 nc의 값을 1 감소시킨다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const delta = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [0, -1]];

function bfs(i, j) {
    let queue = [[i, j]];
    while (queue.length) {
        const [r, c] = queue.shift();
        for (const [dr, dc] of delta) {
            let [nr, nc] = [r+dr, c+dc];
            if (r%2 && dr) nc -= 1;
            if (H > nr && nr >= 0 && W > nc && nc >= 0) {
                if (buildings[nr][nc] == 0) {
                    buildings[nr][nc] = -1;
                    queue.push([nr, nc]);
                }
            }
        }
    }
}

function count(r, c) {
    let cnt = 0;
    for (const [dr, dc] of delta) {
        let [nr, nc] = [r+dr, c+dc];
        if (r%2 && dr) nc -= 1;
        if (H > nr && nr >= 0 && W > nc && nc >= 0) {
            if (buildings[nr][nc] < 0) cnt += 1;
        }
        else cnt += 1;
    }
    return cnt;
}

const [W, H] = input[0].split(' ').map(Number);
let buildings = [];
for (let i=1; i<=H; i++) buildings.push(input[i].split(' ').map(Number));
for (let r of [0, H-1]) {
    for (let c=0; c<W; c++) {
        if (buildings[r][c] == 0) {
            buildings[r][c] = -1;
            bfs(r, c);
        }
    }
}
for (let c of [0, W-1]) {
    for (let r=0; r<H; r++) {
        if (buildings[r][c] == 0) {
            buildings[r][c] = -1;
            bfs(r, c);
        }
    }
}
let res = 0;
for (let r=0; r<H; r++) {
    for (let c=0; c<W; c++) {
        if (buildings[r][c] == 1) res += count(r, c);
    }
}
console.log(res);