백준 1926번 그림

 

정답 :

import Foundation

// 1926번

let num = readLine()!.split(separator: " ").map{Int($0)!}
let row = num[0]
let col = num[1]
var array = [[Int]]()
var queue = [(Int,Int)]()
var visited = Array(repeating: Array(repeating: false, count: col), count: row)
var count = 0
var big = 0

for _ in 0..<row {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    array.append(input)
}

func bfs(array : [[Int]],r : Int,c :Int) {
    var cur_max = 1
    let rowLen = array.count
    let colLen = array[0].count
    let dr = [0, 1, 0, -1]
    let dc = [1, 0, -1, 0]
    
    visited[r][c] = true
    queue.append((r,c))
    while !queue.isEmpty {
        let (cur_r,cur_c) = queue.removeFirst()
        for i in 0..<4 {
            let next_r = cur_r + dr[i]
            let next_c = cur_c + dc[i]
            if 0 <= next_r && next_r < rowLen && 0<=next_c && next_c < colLen {
                if !visited[next_r][next_c] && array[next_r][next_c] == 1 {
                    queue.append((next_r,next_c))
                    visited[next_r][next_c] = true
                    cur_max += 1
                }
            }
        }
    }
    big = max(big, cur_max)
}

for i in 0..<row{
    for j in 0..<col {
        if !visited[i][j] && array[i][j] == 1 {
            bfs(array: array,r: i,c: j)
            count += 1
        }
    }
}
print(count,big)

여담으로 시작!

 

현재 저희 학교에서 주최하는 코딩테스트 특강으로 인해, 지금까지 단계별로 풀어보기 순으로 진행을 하였지만, 배운 것을 바로 써보면서 익히는게 중요하다 생각하여 순서를 바꾸도록 하겠습니다. 배운 것만 먼저 진행하고 그 다음에 다시 돌아가서 순서대로 진행하겠습니다.

 

해당 문제는 BFS를 이용해서 연결된 그림을 찾아가며 그 그림의 크기를 비교하고, 그림의 개수가 몇개인지를 판별하는 문제입니다.

BFS의 가장 큰 특징은 queue를 사용하는 것인데, 이는 우리가 가야할 곳을 예약하고 차례대로 이동하는 것이 특징입니다.

 

그림의 전체 개수는 이중 for문에서 bfs 함수가 불려가는 개수만큼 나오게 되고, 그림의 가장 큰 크기는 bfs가 모두 끝나는 순간에 비교하면 끝!