알고리즘 문제

백준 1926 - 그림(Swift)

레옹아범 2023. 11. 13. 16:03
반응형

백준 1926 - 그림(Swift)

1926번: 그림

접근법

  • 큐 구현(removeFirst의 O(n) 시간복잡도를 피하기 위해서)
  • BFS로 접근
    • 그림의 개수는 (0,0)부터 진행하며 (n,m)까지 탐색
    • 해당 그래프의 위치에서 접근한적이 없으며, 값이 1인 위치가 있을 경우 해당위치에서 다시 BFS를 통해 계산

큐 구현

struct Queue<T> {
    private var enqueueStack: [T] = []
    private var dequeueStack: [T] = []

    var isEmpty: Bool {
        return enqueueStack.isEmpty && dequeueStack.isEmpty
    }

    mutating func enqueue(_ value: T) {
        enqueueStack.append(value)
    }

    mutating func dequeue() -> T? {
        if dequeueStack.isEmpty {
            dequeueStack = enqueueStack.reversed()
            enqueueStack.removeAll()
        }

        return dequeueStack.popLast()
    }
}
  • 두개의 Array로 큐를 구현
  • 좌표를 저장하기 때문에 (x, y)의 튜플을 넣어도 되지만 혹시 실패할 경우 다양한 시도를 위해 미리 제너릭을 이용하여 구현

첫 실패코드

func bfs(_ standardCoordinate: (x: Int, y: Int)) -> Int {
    var queue = Queue<(x: Int, y: Int)>()
    var count = 1

    let dxs = [0, 0, -1, 1]
    let dys = [-1, 1, 0, 0]

    queue.enqueue(standardCoordinate)
    isVisited[standardCoordinate.x][standardCoordinate.y] = true

    while !queue.isEmpty {
        let coordinate = queue.dequeue()!

        for (dx, dy) in zip(dxs, dys) {
            if coordinate.x + dx >= 0 && coordinate.x + dx < maxX &&
                coordinate.y + dy >= 0 && coordinate.y + dy < maxY {

                if !isVisited[coordinate.x + dx][coordinate.y + dy] &&
                    graph[coordinate.x + dx][coordinate.y + dy] == 1 {
                    queue.enqueue((coordinate.x + dx, coordinate.y + dy))
                    isVisited[coordinate.x + dx][coordinate.y + dy] = true
                    answer[coordinate.x + dx][coordinate.y + dy] = answer[coordinate.x][coordinate.y] + 1
                    count += 1
                }
            }
        }
    }

    return count
}

let infos = readLine()!.split(separator: " ").map { Int($0)! }
let maxX = infos[0]
let maxY = infos[1]

var numOfPicture = 0
var graph: [[Int]] = []
var isVisited: [[Bool]] = Array(repeating: Array(repeating: false, count: maxY), count: maxX)
var answer: [[Int]] = Array(repeating: Array(repeating: 0, count: maxY), count: maxX)

for _ in 0..<maxX {
    let arr = readLine()!.split(separator: " ").map { Int($0)! }

    graph.append(arr)
}

for x in 0..<maxX {
    for y in 0..<maxY {
        if !isVisited[x][y] && graph[x][y] == 1 {
            numOfPicture += 1
            answer[x][y] = 1
            bfs((x, y))
        }
    }
}
  • answer을 사용하여 현재 기준점을 1로 BFS를 시도할 때마다 +1하여 answer를 만들었는데 이럴 경우 직사각형의 넓이를 구하기 어려움
[[1, 2, 0, 1, 2],
[0, 3, 4, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 1, 2, 3],
[0, 0, 2, 3, 4],
[0, 0, 3, 4, 5]]
  • 예제의 입력값을 통해 answer를 구할 경우 아래와 같이 나오기 때문에 다른 방법을 사용

두번째 실패 코드

func bfs(_ standardCoordinate: (x: Int, y: Int)) -> Int {
    var queue = Queue<(x: Int, y: Int)>()
    var count = 1

    let dxs = [0, 0, -1, 1]
    let dys = [-1, 1, 0, 0]

    queue.enqueue(standardCoordinate)
    isVisited[standardCoordinate.x][standardCoordinate.y] = true

    while !queue.isEmpty {
        let coordinate = queue.dequeue()!

        for (dx, dy) in zip(dxs, dys) {
            if coordinate.x + dx >= 0 && coordinate.x + dx < maxX &&
                coordinate.y + dy >= 0 && coordinate.y + dy < maxY {

                if !isVisited[coordinate.x + dx][coordinate.y + dy] &&
                    graph[coordinate.x + dx][coordinate.y + dy] == 1 {
                    queue.enqueue((coordinate.x + dx, coordinate.y + dy))
                    isVisited[coordinate.x + dx][coordinate.y + dy] = true
                    count += 1
                }
            }
        }
    }

    return count
}

let infos = readLine()!.split(separator: " ").map { Int($0)! }
let maxX = infos[0]
let maxY = infos[1]

var numOfPicture = 0
var graph: [[Int]] = []
var isVisited: [[Bool]] = Array(repeating: Array(repeating: false, count: maxY), count: maxX)
var areas: [Int] = []

for _ in 0..<maxX {
    let arr = readLine()!.split(separator: " ").map { Int($0)! }

    graph.append(arr)
}

for x in 0..<maxX {
    for y in 0..<maxY {
        if !isVisited[x][y] && graph[x][y] == 1 {
            numOfPicture += 1
            let area = bfs((x, y))
            areas.append(area)
        }
    }
}

print(numOfPicture)
print(areas.max()!)
  • BFS에서 노드가 하나씩 접근할 때마다 +1을 하여 넓이를 출력할 수 있도록 BFS함수를 구현
  • 그리고 여러 넓이를 가져와 가장 큰 값을 출력하도록 만듦

실패 이유

1 1
0
  • 위와 같이 입력값이 주어질 경우 문제가 발생함

최종 코드

import Foundation

struct Queue<T> {
    private var enqueueStack: [T] = []
    private var dequeueStack: [T] = []

    var isEmpty: Bool {
        return enqueueStack.isEmpty && dequeueStack.isEmpty
    }

    mutating func enqueue(_ value: T) {
        enqueueStack.append(value)
    }

    mutating func dequeue() -> T? {
        if dequeueStack.isEmpty {
            dequeueStack = enqueueStack.reversed()
            enqueueStack.removeAll()
        }

        return dequeueStack.popLast()
    }
}

func bfs(_ standardCoordinate: (x: Int, y: Int)) -> Int {
    var queue = Queue<(x: Int, y: Int)>()
    var count = 1

    let dxs = [0, 0, -1, 1]
    let dys = [-1, 1, 0, 0]

    queue.enqueue(standardCoordinate)
    isVisited[standardCoordinate.x][standardCoordinate.y] = true

    while !queue.isEmpty {
        let coordinate = queue.dequeue()!

        for (dx, dy) in zip(dxs, dys) {
            if coordinate.x + dx >= 0 && coordinate.x + dx < maxX &&
                coordinate.y + dy >= 0 && coordinate.y + dy < maxY {

                if !isVisited[coordinate.x + dx][coordinate.y + dy] &&
                    graph[coordinate.x + dx][coordinate.y + dy] == 1 {
                    queue.enqueue((coordinate.x + dx, coordinate.y + dy))
                    isVisited[coordinate.x + dx][coordinate.y + dy] = true
                    count += 1
                }
            }
        }
    }

    return count
}

let infos = readLine()!.split(separator: " ").map { Int($0)! }
let maxX = infos[0]
let maxY = infos[1]

var numOfPicture = 0
var graph: [[Int]] = []
var isVisited: [[Bool]] = Array(repeating: Array(repeating: false, count: maxY), count: maxX)
var areas: [Int] = []

for _ in 0..<maxX {
    let arr = readLine()!.split(separator: " ").map { Int($0)! }

    graph.append(arr)
}

for x in 0..<maxX {
    for y in 0..<maxY {
        if !isVisited[x][y] && graph[x][y] == 1 {
            numOfPicture += 1
            let area = bfs((x, y))
            areas.append(area)
        }
    }
}

print(numOfPicture)
print(areas.max() ?? 0)
반응형