BOJ1080 행렬

출처: www.acmicpc.net/problem/1080

분류: Greedy

---

접근방식

두 형렬에서 한 행렬을 한번에 3x3 만큼씩 뒤집는 연산을 통해 같은 행렬을 만들 수 있는 최소 연산횟수를 구하는 문제입니다.

처음엔 dfs로 무식하게 모든 경우를 다 해봤는데 이럴 경우 엄청난 연산 횟수로 역시 시간초과가 납니다.

그리디 문제인 만큼 그리디하게 풀면 생각보다 쉽게 해결할 수 있습니다. 

0,0 부터 시작해서 n-3까지 가면서 해당 지점이 타겟 행렬과 다르다면 뒤집어줍니다.

0,0부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다.

같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다.

 

이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 만들 수 없는 경우입니다.

(n, m) 행렬의 0,0 행렬부터 시작해서 (0, m-3)까지 갔으면, 현재 0번 행에서는 바꿀 수 있는 최대한을 한 것이죠.

여기서 나머지 (0, m-2), (0, m-1) 중에 타겟 행렬과 다른 것이 있다면 이 경우는 결코 타겟 행렬로 바꿀 수가 없습니다.

그리고 애초에 행렬이 3x3 보다 작다면 뒤집을 수가 없습니다. 이 경우엔 그냥 두 행렬이 같은지 다른지 체크해주고 넘어가면 됩니다.

 

해결방법

import Foundation

let input = readLine()!.components(separatedBy: " ").map{Int($0)!}
var changableBoard = [[Int]](repeating: [], count: input[0])
var targetBoard = [[Int]](repeating: [], count: input[0])
var count = 0

for i in 0..<input[0] * 2 {
    let row = readLine()!
    if i < input[0] {
        for c in row {
            changableBoard[i].append(Int(String(c))!)
        }
    } else {
        for c in row {
            targetBoard[i-input[0]].append(Int(String(c))!)
        }
    }
}

func reverseBoard(_ board: inout [[Int]], _ row: Int, _ col: Int) {
    for r in row..<row+3 {
        for c in col..<col+3 {
            board[r][c] = board[r][c] == 0 ? 1 : 0
        }
    }
}

func changeBoard() {
    if input[0] < 3 || input[1] < 3 { return }
    
    for r in 0..<input[0]-2 {
        for c in 0..<input[1]-2 {
            if changableBoard[r][c] != targetBoard[r][c] {
                reverseBoard(&changableBoard, r, c)
                count += 1
            }
            
            if c == input[1]-3 {
                for i in input[1]-3..<input[1] {
                    // 현재 행에서 최대한으로 바꿨는데도 바꾸지 못하는 열이 남아있다면 바꿀 수 없음
                    if changableBoard[r][i] != targetBoard[r][i] { return }
                }
            }
        }
    }
    
}

func main() {
    changeBoard()
    if changableBoard == targetBoard {
        print(count)
    } else {
        print(-1)
    }
}

main()

 

 

 

쉽지않습니당.. 화이팅...