[swift] 백준 - 1780번: 종이의 개수

1780번: 종이의 개수

---

성공 풀이

let N = Int(readLine()!)!
var arr = [[Int]]()
var cnt = [0,0,0]
for _ in 0..<N {
    arr.append(readLine()!.split(separator: " ").map { Int($0)! })
}

func solution(paperSize: Int, y: Int, x: Int) {
    let point = arr[y][x]
    
    for i in y..<y+paperSize {
        for j in x..<x+paperSize {
            
            if arr[i][j] != point {
                let newSize = paperSize / 3
                
                for k in 0..<3 {
                    for l in 0..<3 {
                        solution(paperSize: newSize, y: y+k*newSize, x: x+l*newSize)
                    }
                }
                return
            }
        }
    }
    cnt[point+1] += 1
}
solution(paperSize: N, y: 0, x: 0)
cnt.forEach { print($0) }

풀이 키워드

분할정복
입력값 N에 9를 받는다면
9*9 크기의 종이(배열)가 만들어집니다.

시작점

9*9 배열이 모두 같은 숫자인지 확인하기 위해
매개변수로 주어지는 (y, x) 값을 이용해
시작점의 숫자(-1 or 0 or 1)를 기억합니다.

다음 0.. <9(paperSize)까지 이중 반복하며

for i in y..<y+paperSize {
        for j in x..<x+paperSize {
            
            if arr[i][j] != point {

arr [i][j]가 시작점의 숫자인지 비교합니다.
만약 시작점과 다르다면
paperSize는 / 3으로 나눠 newSize를 준비해 줍니다.
이 과정은 종이를 같은 크기로 9 개 자르고, 각각 잘린 종이의 크기를 지정해 줍니다.

같은 크기의 9개 종이를 탐색하기 위해
y축을 0..<3, x축을 0..<3 
이중 반복합니다.

                let newSize = paperSize / 3
                
                for k in 0..<3 {
                    for l in 0..<3 {
                        solution(paperSize: newSize, y: y+k*newSize, x: x+l*newSize)
                    }
                }

 

새로운 solution함수를 재귀호출합니다.
현재 newSize는 3
k와 l을 newSize에 곱해 y와 x의 시작점을 초기화시켜줍니다.

시작점이 다를 때는 상위 이중 반복문을 꼭 return 시켜줍니다.
검사 범위에서 시작점과 모든 값이 같다면
cnt 배열의 알맞은 ponit를 1 더 해줍니다.

		return
            }
        }
    }
    cnt[point+1] += 1

 

 

---