1080번: 행렬

문제 풀이 아이디어

브루탈 포스?

아마 맨 처음에 문제를 보면 dfs 같은 완전탐색 알고리즘을 통해서 모든 경우의 수를 계산해야하는 것이 아닌가라는 생각이 들 수 있습니다. 하지만 N과 M이 최대 50이고 이렇게 되면 행렬의 원소의 사이즈는 최대 2500이 됩니다. 그리고 행렬의 원소 마다 연산을 실행하거나 안하는 경우의 수까지 고려하면 연산의 횟수가 지나치게 커지게 됩니다.

그리디!

해결 방법은 그리디 알고리즘입니다.

문제에서 주어진 연산을 구체적으로 풀어쓰자면 r행 c열을 기준으로 3 x 3 크기의 행렬의 원소를 뒤집는 것입니다. 더 구체적으로 말씀드리면 r행 ~ (r + 2)행, c행 ~ (c + 2)행의 행렬의 원소를 뒤집는 것이죠.

A행렬의 (0, 0)에서부터 반복문으로 모든 행, 열을 탐색하면서 B의 동일한 행, 열의 원소와 다른 원소가 있으면 그 행, 열에서 연산을 수행해야 합니다. 왜냐하면 현재의 행, 열은 앞으로 반복문이 진행되면서 다른 연산이 수행된다고 하더라도 영향을 받는 일은 없습니다.

다른 말로 하면 반드시 연산을 수행해야 A와 B를 동일하게 할 수 있다는 것이죠. 따라서 현재 상황에 가장 최적의 연산을 수행해야 하는 그리디 알고리즘의 개념으로 접근할 수 있는 것입니다.

코드

// 행렬

// 원소를 뒤집는 extension
extension Int {
    mutating func toggle() {
        switch self {
        case 0: self = 1; return
        case 1: self = 0; return
        default: return
        }
    }
}

// 두 행렬이 동일한지 확인하기 위해서 == 구현
    // 모든 원소가 동일하면 true 하나라도 틀리면 false
extension Array where Element == [Int] {
    static func ==(lhs: [[Int]], rhs: [[Int]]) -> Bool {
        for i in 0..<N {
            for j in 0..<M {
                if lhs[i][j] != rhs[i][j] { return false }
            }
        }
        return true
    }
}

// 3 x 3 사이즈의 행렬의 원소를 뒤집는 연산
func f(_ r: Int, _ c: Int) {
    // r행, c열을 (0, 0)으로 하는 3 x 3 행렬을 구할 수 없다면 실행하지 않음
    guard r + 2 < N && c + 2 < M else { return }
    for i in r..<(r + 3) {
        for j in c..<(c + 3) {
            A[i][j].toggle()
        }
    }
}

// 입력
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]

var A = [[Int]]()
var B = [[Int]]()

for _ in 0..<N {
    A.append(readLine()!.map { Int(String($0))! })
}

for _ in 0..<N {
    B.append(readLine()!.map { Int(String($0))! })
}

// 연산의 횟수 정하기
var cnt = 0

// 그리디 연산 수행: r행 c열의 A와 B의 원소가 다르면 그 점을 기준으로 연산 실행
for r in 0..<N {
    for c in 0..<M {
        if A[r][c] != B[r][c] {
            f(r, c)
            cnt += 1
        }
    }
}

// 최종적으로 동일하게 만들 수 있으면 cnt, 안되면 -1
if A == B {
    print(cnt)
} else {
    print(-1)
}