[Algorithm] 백준 - 1080번 행렬 (Swift)

문제 소개

행렬을 뒤집어서 A, B를 같게 만드는 문제이다.
 

문제 풀이

행렬 A, B 를 입력받고 다른 부분을 1로 하는 새로운 diff 행렬을 만든다. 배열을 순회하면서 1이 있으면 행렬을 뒤집는다. 행렬을 뒤집을때마다 count를 세고, 만약 남은 diff 행렬에 1이 남아있을때 -1을 출력하고 diff 행렬이 모두 0이면 count를 출력한다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var a = [[Int]]()
var b = [[Int]]()

// A, B 행렬 입력
for _ in 0..<n {
    let input = Array(readLine()!).map { Int(String($0))! }
    a.append(input)
}

for _ in 0..<n {
    let input = Array(readLine()!).map { Int(String($0))! }
    b.append(input)
}

// 행렬이 다른 경우 1을 입력
var diff = Array(repeating: Array(repeating: 0, count: m), count: n)

for i in 0..<n {
    for j in 0..<m {
        if a[i][j] != b[i][j] {
            diff[i][j] = 1
        }
    }
}

// 행렬 뒤집기
var count = 0

func flip(_ i: Int, _ j: Int) {
    if i+3 <= n && j+3 <= m {
        count += 1
        for i in i..<i+3 {
            for j in j..<j+3 {
                if diff[i][j] == 0 {
                    diff[i][j] = 1
                } else {
                    diff[i][j] = 0
                }
            }
        }
    }
}

for i in 0..<n {
    for j in 0..<m {
        if diff[i][j] == 1 {
            flip(i, j)
        }
    }
}

// diff 행렬 순회, 결과 값 출력
var answer = 0

loop: for i in 0..<n {
    for j in 0..<m {
        if diff[i][j] == 1 {
            answer = -1
            break loop
        }
    }
}

print(answer == 0 ? count : answer)

 
아래와 같이 12ms로 아주 빠른 결과가 나왔다. 시간복잡도는 O(m*n) 이다.