[필수] 2630 색종이 만들기 [이차원 리스트][재귀]

정답 코드

let N = Int(readLine()!)!
var arr: [[Int]] = []

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

var white = 0
var blue = 0

func divideConquer(_ r: Int, _ c: Int, _ n: Int) {
    let color = arr[r][c]
    
    for i in r..<r + n {
        for j in c..<c + n {
            if color != arr[i][j] {
                divideConquer(r, c, n / 2)
                divideConquer(r, c + n / 2, n / 2)
                divideConquer(r + n / 2, c, n / 2)
                divideConquer(r + n / 2, c + n / 2, n / 2)
                return
            }
        }
    }
    
    if color == 0 {
        white += 1
    } else {
        blue += 1
    }
}


divideConquer(0, 0, N)

print(white)
print(blue)

 

코드 설명

• divideConquer함수 [이중 for문을 탈출하기 위해 함수를 만들었습니다.]
  • (0,0)값을 color에 저장하고 color와 다른 값이 있으면 4등분해서 다시 divideConquer함수로 재귀를 한다.
  • if문 내에서 순서대로 4등분 기준으로 왼쪽 상단, 오른쪽  상단, 왼쪽 하단, 오른쪽 하단을 계산한 뒤 return한다
• 재귀를 타지 않는다면 조건문에 따라 white나 blue의 수를 증가 시켜줍니다.

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기