Swift - 백준 1012번 유기농 배추

유기농 배추 문제는 DPS 문제로 해결할 수 있습니다

 

 

처음 문제를 해결할 때 가장 헷갈렸던 부분은 2차원 배열을 생성하는 과정이였습니다. 2차원 배열을 만드려면 다음과 같습니다.

var array = Array(repeating: Array(repeating: 0, count: columns), count: rows)

 

2차원 배열을 만든 다음으로는 재귀함수를 이용한 DPS를 통해 문제를 해결할 수 있었습니다.

func find(row: Int, column: Int) {
    array[row][column] = 0
    if column-1 > -1 && array[row][column-1] == 1 {
        find(row: row, column: column-1)
    }
    if column+1 < columns && array[row][column+1] == 1 {
        find(row: row, column: column+1)
    }
    if row+1 < rows && array[row+1][column] == 1 {
        find(row: row+1, column: column)
    }
    if row-1 > -1 && array[row-1][column] == 1 {
        find(row: row-1, column: column)
    }
}

 

 

전체 코드

import Foundation

let num = Int(readLine()!)!


for _ in 1...num {
    var tc = readLine()!.split(separator: " ").map { Int($0)! }
    var rows = tc[1] // 행
    var columns = tc[0] // 열
    var array = Array(repeating: Array(repeating: 0, count: columns), count: rows)
    
    func find(row: Int, column: Int) {
        array[row][column] = 0
        if column-1 > -1 && array[row][column-1] == 1 {
            find(row: row, column: column-1)
        }
        if column+1 < columns && array[row][column+1] == 1 {
            find(row: row, column: column+1)
        }
        if row+1 < rows && array[row+1][column] == 1 {
            find(row: row+1, column: column)
        }
        if row-1 > -1 && array[row-1][column] == 1 {
            find(row: row-1, column: column)
        }
    }
    for _ in 1...tc[2] {
        let tmp = readLine()!.split(separator: " ").map { Int($0)! }
        array[tmp[1]][tmp[0]] = 1
    }
    
    var count = 0
    
    for i in 0..<rows {
        for j in 0..<columns {
            if array[i][j] == 1 {
                find(row: i, column: j)
                count+=1
            }
        }
    }
    print(count)
}