BOJ-1780 종이의 개수 Swift

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

내가 푼 풀이

접근방법: 분할정복

1. 주어진 배열이 모두 같은원소로 이루어졌는지 판단

2. 이루어지지 않았다면 해당배열을 같은크기의 배열 9등분으로 나눔

3. 모두 같은원소로 이루어질때 까지 1-2 반복(재귀호출)

4. 같은원소로 이루어졌다면 해당 원소에따라 다르게 저장

5. 저장된 값을 출력

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력
let N = Int(readLine()!)!
var arr = [[String]]()
arr.append(["0"])
var result = [0,0,0]
for i in 0..<N {
    var a = readLine()!.split(separator: " ").map{String($0)}
    a.insert("0", at: 0)
    arr.append(a)
}

// 분할
func divide(_ xs: Int,_ xe: Int,_ ys: Int,_ ye: Int,_ arr: [[String]],_ N: Int) {
    if !check(xs, xe, ys, ye, arr) {
        let m = N/3
        // 9가지로 분할, 해당 분할 위치에따른 재귀호출
        // [1, 2, 3]
        // [4, 5, 6]
        // [7, 8, 9]
        
        // 1
        divide(xs, xs+m-1, ys, ys+m-1, arr, N/3)
        // 2
        divide(xs+m, xs+m*2-1, ys, ys+m-1, arr, N/3)
        // 3
        divide(xs+m*2, xe, ys, ys+m-1, arr, N/3)
        // 4
        divide(xs, xs+m-1, ys+m, ys+m*2-1, arr, N/3)
        // 5
        divide(xs+m, xs+m*2-1, ys+m, ys+m*2-1, arr, N/3)
        // 6
        divide(xs+m*2, xe, ys+m, ys+m*2-1, arr, N/3)
        // 7
        divide(xs, xs+m-1, ys+m*2, ye, arr, N/3)
        // 8
        divide(xs+m, xs+m*2-1, ys+m*2, ye, arr, N/3)
        // 9
        divide(xs+m*2, xe, ys+m*2, ye, arr, N/3)
    }
}

// 같은 원소로 이루어졌는지 확인
func check(_ xs: Int,_ xe: Int,_ ys: Int,_ ye: Int,_ arr: [[String]]) -> Bool{
    let val = arr[ys][xs]
    for i in ys...ye {
        for j in xs...xe {
            if val != arr[i][j] { return false }
        }
    }
    // 해당 원소의 따라 다르게 저장
    switch val {
    case "-1": result[0] += 1
    case "0": result[1] += 1
    case "1": result[2] += 1
    default:
        break
    }
    return true
}

// 실행 및 출력
divide(1, N, 1, N, arr, N)
print("\(result[0])\n\(result[1])\n\(result[2])\n")