백준 1926 그림

출처: https://www.acmicpc.net/problem/1926

분류: BFS

---

접근방식

BFS 방식으로 풀어봤습니다.

bfs를 시작하면서 그림의 개수를 세고, bfs 안에서 queue에서 꺼낼 때마다 카운트 해서 그림의 너비를 계산했습니다.

queue는 DoubleStackQueue를 사용했습니다.

 

해결방법

struct DoubleStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []

    var isEmpty: Bool{
        return inbox.isEmpty && outbox.isEmpty
    }

    var count: Int{
        return inbox.count + outbox.count
    }

    var front: Element? {
        return outbox.last ?? inbox.first
    }

    init() { }

    init(_ array: [Element]) {
        self.init()
        self.inbox = array
    }

    mutating func enqueue(_ n: Element) {
        inbox.append(n)
    }

    mutating func dequeue() -> Element? {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        guard !outbox.isEmpty else { return nil }
        return outbox.removeLast()
    }
}

extension DoubleStackQueue: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self.init()
        inbox = elements
    }
}

// MARK: - Solution

struct Point {
    var row: Int
    var col: Int
    var value = 1
    
    var moves: [Point] {
        return [
            Point(row-1, col),
            Point(row+1, col),
            Point(row, col-1),
            Point(row, col+1)
        ]
    }
    
    func isInRange(r rows: Range<Int>, c cols: Range<Int>) -> Bool {
        return rows.contains(row) && cols.contains(col)
    }
    
    init(_ row: Int, _ col: Int) {
        self.row = row
        self.col = col
    }
}

var data = readLine()!.split(separator: " ").map { Int($0)! }
let r = data[0]
let c = data[1]
var numberOfPicture = 0
var maxWidth = 0

var board = [[Int]]()
for _ in 0..<r {
    board.append(readLine()!.split(separator: " ").map({ Int($0)! }))
}

var visited = [[Bool]](repeating: [Bool](repeating: false, count: c), count: r)

func bfs(_ p: Point) {
    var queue = DoubleStackQueue<Point>()
    queue.enqueue(p)
    visited[p.row][p.col] = true
    var currentWidth = 1
    
    while !queue.isEmpty {
        let curr = queue.dequeue()!
        if currentWidth > maxWidth {
            maxWidth = currentWidth
        }
        for next in curr.moves where next.isInRange(r: 0..<r, c: 0..<c)  {
            guard board[next.row][next.col] == 1, !visited[next.row][next.col] else { continue }
            visited[next.row][next.col] = true
            currentWidth += 1
            var next = next
            next.value = currentWidth
            queue.enqueue(next)
        }
    }
}

for r in 0..<r {
    for c in 0..<c {
        guard !visited[r][c], board[r][c] == 1 else { continue }
        bfs(Point(r, c))
        numberOfPicture += 1
    }
}

print(numberOfPicture)
print(maxWidth)

회고

 

BFS를 풀 때 만큼은 기계가 되자 .