문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
- 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
- (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")'코딩테스트 > 백준' 카테고리의 다른 글
| BOJ-11401 이항 계수 3 Swift (0) | 2024.05.03 |
|---|---|
| BOJ-1629 곱셈 Swift (0) | 2024.05.03 |
| BOJ-1992 쿼드트리 Swift (0) | 2024.05.03 |
| BOJ-10986 나머지 합 Swift (1) | 2024.05.02 |
| BOJ-11659 구간 합 구하기 4 Swift (1) | 2024.05.01 |
