[Swift 알고리즘] 백준 BOJ - 1012 유기농 배추

안녕하세요. 개발 중인 정주입니다.

 

오늘은 백준 BOJ - 1012 유기농 배추 문제를 풀었습니다.

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1012번: 유기농 배추

 

---

풀이

이번 문제는 DFS를 이용해 풀 수 있는 문제입니다.

 

상하좌우에 방문하지 않았고 배추가 심긴 곳이 있다면 이동합니다.

새로운 진입 지점을 찾을 때마다 count를 1 증가시킵니다.

 

진입하면 상하좌우 연결된 모든 곳을 탐색하기 때문에 새로운 진입 지점이 곧 필요한 배추 흰 지렁이 수입니다.

 

---

전체 코드

import Foundation

let count = Int(readLine()!)!

var farmW = 0, farmH = 0
var farm: [[Bool]] = []

let dx: [Int] = [0, 0, -1, 1]
let dy: [Int] = [-1, 1, 0, 0]

for _ in 0..<count {
    //input
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    farmW = input[0]
    farmH = input[1]
    let cabbageCount = input[2]
    
    farm = Array(repeating: Array(repeating: false, count: farmW), count: farmH)
    for _ in 0..<cabbageCount {
        let positions = readLine()!.split(separator: " ").map { Int(String($0))! }
    
        farm[positions[1]][positions[0]] = true
    }
    
    var count = 0
    for y in 0..<farmH {
        for x in 0..<farmW {
            if farm[y][x] {
                dfs(y: y, x: x)
                count += 1
            }
        }
    }
    
    print(count)
}

func dfs(y: Int, x: Int) {
    if farm[y][x] {
        farm[y][x] = false
        
        for i in 0..<4 {
            let nextY = y + dy[i], nextX = x + dx[i]
            if nextY >= 0 && nextY < farmH && nextX >= 0 && nextX < farmW {
                if farm[y+dy[i]][x+dx[i]] {
                    dfs(y: y+dy[i], x: x+dx[i])
                }
            }
        }
    }
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.