[Swift] 백준_그림(1926)

문제

 

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

1926번: 그림

 

 

풀이

 

BFS로 해결할 수 있는 문제였고, 익숙하지가 않아서 어려웠다.

 

 

반복문을 통해 보드를 하나씩 이동하며 방문하지 않은(visited가 false) 자리이고, paper[i][j]가 1인 경우에 BFS를 통해 그림을 확인하였다.

 

BFS를 수행하는 과정은 다음과 같다.

 

우선, 큐에 해당 위치인 [i][j]를 넣어준다. 

다음으로 [i][j]를 방문했으므로 visited[i][j]를 true로 바꿔준다.

마지막으로 queue 원소의 위, 아래, 양 옆을 확인하여 1이 있다면 그 위치를 다시 queue에 넣는 작업을 queue가 빌 때까지 반복해주었다.

마찬가지로 방문한 노드에 대해서는 visited의 값을 true로 바꿔주었따.

 

이렇게 하나의 그림을 확인한 뒤에 바깥의 반복문을 통해 이후에도 그림이 있는지 확인하게 된다.

이때, 방문했던 노드는 다시 확인하지 않아야 반복작업이 없으므로 방문했는지 확실하게 체크해주는 것이 중요했다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var paper: [[String]] = []
for _ in 0..<input[0] {
    paper.append(readLine()!.split(separator: " ").map { String($0) })
}
var visited = Array(repeating: Array(repeating: false, count: input[1]),count: input[0])
var queue: [[Int]] = []
var maxArea = 0
var count = 0
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]

for i in 0..<input[0] {
    for j in 0..<input[1] {
        if visited[i][j] || paper[i][j] == "0" {
            continue
        }
        //BFS
        queue.append([i,j])
        visited[i][j] = true
        count += 1
        var area = 0
        while !queue.isEmpty {
            let current = queue.removeFirst()
            area += 1
            for k in 0..<dx.count {
                let newX = current[0] + dx[k]
                let newY = current[1] + dy[k]
                if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
                    continue
                }
                if visited[newX][newY] || paper[newX][newY] != "1" {
                    continue
                }
                queue.append([newX, newY])
                visited[newX][newY] = true
            }
        }
        maxArea = max(maxArea, area)
    }
}
print(count, maxArea)

 

_____________________________________________________________________________________________________

 

BFS에 얼른 익숙해져야할듯

 

개념은 이해가 가지만 구현을 하는 것이 쉽지 않다.