문제 링크 (opens new window)

문제 설명

1. 6방향으로 인접한 건물 각 그룹의 외벽 총 길이를 합산해야 한다.
2. 내벽은 계산하지 않고 인접한 건물 한 그룹 내에 비어있는 건물 위치에서도 크기에 상관 없이 벽 갯수로 계산하지 않아야 한다.

잘못된 초기 접근 방식

1. 건물 입력 과정에서 건물들에 둘러쌓인 내벽을 1로 초기화해주어 아예 하나의 건물 단지로 만드는 로직을 생각했음
2. 둘러쌓인 내벽이란, 입력값이 0이면서 6방향 순회 시 전체 입력이 1인 경우를 말한다.
3. 반례의 경우, 입력값이 0으로 연속하여 두 위치에 입력되는 경우 6방향 순회가 1이 되지 않는다. 한 곳은 뚫려있지만 여전히 내벽으로 간주해야 한다.

올바른 접근 방식

1. 건물 입력에 외부 테두리를 추가한다.
2. 테두리 아무 위치에서부터 DFS를 시작하여 입력값이 1로 접근이 이루어질 때 리턴값을 1 더해준다. (edge 갯수 하나 증가)
3. for문으로 순회 시 문제 조건에 맞추어 (x, y+1) 좌표 변화량을 홀수 짝수에 맞춰 제대로 반영해야 한다.

풀이

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let WH = readLine()!.split(separator: " ").map { Int($0)! }; let W = WH[0]; let H = WH[1]
let dy = [-1, -1, 0, 1, 1, 0]; let dxOdd = [0, 1, 1, 1, 0, -1]; let dxEven = [-1, 0, 1, 0, -1, -1]

var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: W+2), count: H+2)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: W+2), count: H+2)
var ret = 0

for i in 1...H {
    var row: [Int] = [0]
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    row += input + [0]
    adj[i] = row
}

// 밖에서 DFS 순회 - 외벽 좌표 추가
func dfs(_ y: Int, _ x: Int) {
    visited[y][x] = true

    for i in 0..<6 {
        let ny = dy[i] + y
        var nx = 0
        if y % 2 == 1 {
            nx = dxOdd[i] + x
        } else {
            nx = dxEven[i] + x
        }

        if ny < 0 || nx < 0 || ny > H+1 || nx > W+1 || visited[ny][nx] {
            continue
        }

        if adj[ny][nx] == 1 {
            ret += 1
            continue
        }

        dfs(ny, nx)
    }
}

dfs(0, 0)
print(ret)