[Swift] 백준_유기농 배추(1012)

문제

 

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

1012번: 유기농 배추

 

 

풀이

 

일반적인 BFS문제였다.

 

우선, ground라는 변수를 만들어 배추가 어디에 있는지 표시를 한다.

이 배추들을 차례대로 반복문을 통해 방문할텐데 방문했다는 표시를 하기 위해 visited변수를 만들어주었다.

 

이제 반복문을 돌다가 1(배추)를 만나면 그 자리에서 BFS를 돌린다. 지렁이는 인접한 배추끼린 하나만 필요하므로 해당 배추 주변을 상하좌우로 확인하면서 방문하지 않은 1인 경우엔 큐에 넣어 다시 while문을 돌게 하였다.

while문을 돌때마다 count를 증가시켜주면 지렁이가 얼마나 필요한지 알 수 있다.

import Foundation

let caseCount = Int(readLine()!)!
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
for _ in 0..<caseCount {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    var ground = Array(repeating: Array(repeating: 0, count: input[1]), count: input[0])
    var visited = Array(repeating: Array(repeating: 0, count: input[1]), count: input[0])
    var count = 0
    var queue: [[Int]] = []
    for _ in 0..<input[2] {
        let position = readLine()!.split(separator: " ").map { Int(String($0))! }
        ground[position[0]][position[1]] = 1
    }
    for i in 0..<input[0] {
        for j in 0..<input[1] {
            if ground[i][j] == 0 || visited[i][j] == 1 {
                continue
            }
            queue.append([i,j])
            visited[i][j] = 1
            count += 1
            var idx = 0
            while idx < queue.count {
                let current = queue[idx]
                idx += 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 ground[newX][newY] == 0 || visited[newX][newY] == 1 {
                        continue
                    }
                    queue.append([newX,newY])
                    visited[newX][newY] = 1
                }
            }
        }
    }
    print(count)
}

 

_____________________________________________________________________________________________________

 

다른 풀이를 보면 시간이 더 적게 걸린 풀이들도 있어서 풀리더라도 더 줄일 수 있도록 해봐야할듯