문제 요약
직사각형 공간에 앞면과 뒷면이 있는 동전이 놓여 있다.
한 번의 동작으로 행 하나 또는 열 하나에 있는 모든 동전을 뒤집을 수 있다.
초기 상태 beginning을 목표 상태 target으로 만들기 위해 필요한 최소 뒤집기 횟수를 구해야 한다.
목표 상태를 만들 수 없다면 -1을 반환한다.
핵심 아이디어
각 칸에서 초기 상태와 목표 상태가 다른지 먼저 확인한다.
beginning[r][c] == target[r][c] : 뒤집지 않아야 함
beginning[r][c] != target[r][c] : 홀수 번 뒤집혀야 함행 r을 뒤집는지 여부를 row_flip[r], 열 c를 뒤집는지 여부를 col_flip[c]라고 하자.
한 칸은 자신의 행과 열이 뒤집힐 때마다 뒤집힌다.
따라서 해당 칸이 최종적으로 뒤집히는 횟수의 홀짝은 다음과 같다.
row_flip[r] XOR col_flip[c]초기 상태와 목표 상태의 차이를 difference[r][c]라고 하면 모든 칸은 다음 조건을 만족해야 한다.
row_flip[r] XOR col_flip[c] == difference[r][c]이 식을 이용하면 첫 번째 행을 뒤집는지 여부만 정하면 나머지 행과 열의 뒤집기 여부가 모두 결정된다.
첫 번째 행은 뒤집거나 뒤집지 않는 두 가지 경우뿐이다.
따라서 두 경우를 모두 확인하고 가능한 경우 중 뒤집기 횟수가 더 작은 값을 선택한다.
차이 행렬 만들기
두 상태가 다르면 1, 같으면 0이 되도록 XOR 연산을 사용한다.
difference = [
[
beginning[row][column] ^ target[row][column]
for column in range(column_count)
]
for row in range(row_count)
]예를 들어 초기값이 0이고 목표값이 1이면 XOR 결과는 1이다.
0 XOR 1 = 1초기값과 목표값이 같으면 XOR 결과는 0이다.
0 XOR 0 = 0
1 XOR 1 = 0첫 번째 행을 기준으로 결정하기
첫 번째 행을 뒤집는지 여부를 first_row_flip이라고 하자.
row_flip[0] = first_row_flip첫 번째 행의 각 칸은 다음 조건을 만족해야 한다.
row_flip[0] XOR col_flip[c] == difference[0][c]따라서 각 열의 뒤집기 여부는 다음과 같이 결정된다.
col_flip[c] = difference[0][c] ^ row_flip[0]이제 첫 번째 열을 이용해 나머지 모든 행의 뒤집기 여부를 결정할 수 있다.
row_flip[r] XOR col_flip[0] == difference[r][0]따라서 다음과 같다.
row_flip[r] = difference[r][0] ^ col_flip[0]모든 칸 검증
첫 번째 행과 첫 번째 열을 기준으로 정한 값이 모든 칸에서도 조건을 만족하는지 확인해야 한다.
if (
row_flip[row] ^ col_flip[column]
!= difference[row][column]
):
return impossible한 칸이라도 조건을 만족하지 못하면 해당 첫 번째 행 선택으로는 목표 상태를 만들 수 없다.
풀이 과정
1. 두 상태의 차이 행렬 계산
difference[row][column] = (
beginning[row][column]
^ target[row][column]
)2. 첫 번째 행을 뒤집지 않는 경우 확인
count_flips(0)3. 첫 번째 행을 뒤집는 경우 확인
count_flips(1)4. 가능한 두 경우 중 최솟값 반환
answer = min(count_flips(0), count_flips(1))두 경우 모두 불가능하면 -1을 반환한다.
Python 코드
def solution(beginning, target):
row_count = len(beginning)
column_count = len(beginning[0])
INF = float("inf")
difference = [
[
beginning[row][column] ^ target[row][column]
for column in range(column_count)
]
for row in range(row_count)
]
def count_flips(first_row_flip):
row_flip = [0] * row_count
col_flip = [0] * column_count
# 첫 번째 행을 뒤집는지 여부를 가정한다.
row_flip[0] = first_row_flip
# 첫 번째 행 조건으로 모든 열의 뒤집기 여부를 정한다.
for column in range(column_count):
col_flip[column] = (
difference[0][column]
^ row_flip[0]
)
# 첫 번째 열 조건으로 나머지 행의 뒤집기 여부를 정한다.
for row in range(1, row_count):
row_flip[row] = (
difference[row][0]
^ col_flip[0]
)
# 모든 칸이 목표 상태가 되는지 검증한다.
for row in range(row_count):
for column in range(column_count):
if (
row_flip[row] ^ col_flip[column]
!= difference[row][column]
):
return INF
return sum(row_flip) + sum(col_flip)
answer = min(count_flips(0), count_flips(1))
return -1 if answer == INF else answer코드 설명
difference
difference[row][column]해당 칸을 홀수 번 뒤집어야 하는지 나타낸다.
값이 0이면 행과 열 뒤집기의 총횟수가 짝수여야 하고, 값이 1이면 홀수여야 한다.
첫 번째 행의 두 가지 경우
count_flips(0)
count_flips(1)첫 번째 행은 뒤집지 않거나 뒤집는 두 선택만 가능하다.
한 번 선택하면 첫 번째 행의 조건으로 모든 열이 결정되고, 첫 번째 열의 조건으로 나머지 행이 결정된다.
따라서 가능한 조합을 지수적으로 탐색할 필요가 없다.
열 뒤집기 결정
col_flip[column] = (
difference[0][column]
^ row_flip[0]
)첫 번째 행의 각 칸이 목표 상태가 되도록 열의 뒤집기 여부를 정한다.
XOR는 같은 값이면 0, 다른 값이면 1이므로 행 뒤집기 여부를 알고 있을 때 필요한 열 뒤집기 여부를 바로 구할 수 있다.
행 뒤집기 결정
row_flip[row] = (
difference[row][0]
^ col_flip[0]
)첫 번째 열의 각 칸이 목표 상태가 되도록 나머지 행의 뒤집기 여부를 정한다.
전체 검증
row_flip[row] ^ col_flip[column]
!= difference[row][column]첫 번째 행과 열의 조건은 맞더라도 내부 칸에서 모순이 생길 수 있다.
그래서 모든 칸을 확인해 실제로 목표 상태를 만들 수 있는지 검증해야 한다.
예시
차이 행렬이 다음과 같다고 하자.
0 1 0
1 0 1
0 1 0첫 번째 행을 뒤집지 않는다고 가정한다.
row_flip[0] = 0첫 번째 행을 기준으로 열 뒤집기 여부는 다음과 같이 결정된다.
col_flip = [0, 1, 0]첫 번째 열을 기준으로 행 뒤집기 여부는 다음과 같이 결정된다.
row_flip = [0, 1, 0]모든 칸에서 행과 열의 XOR가 차이 행렬과 같으므로 목표 상태를 만들 수 있다.
뒤집기 횟수는 다음과 같다.
행 1개 + 열 1개 = 2회시간 복잡도
행의 수를 N, 열의 수를 M이라고 하자.
첫 번째 행에 대한 두 가지 경우를 각각 확인한다.
각 경우에서 행과 열을 결정하고 모든 칸을 한 번 검증한다.
O(N x M)두 번 수행하더라도 상수 배만 증가한다.
공간 복잡도
차이 행렬, 행 뒤집기 배열, 열 뒤집기 배열을 사용한다.
O(N x M)차이 행렬을 만들지 않고 beginning과 target을 직접 XOR하면 추가 공간을 줄일 수도 있다.
정리
이 문제는 행과 열 뒤집기 여부를 0과 1로 표현한 XOR 방정식 문제다.
초기 상태와 목표 상태의 XOR로 차이 행렬 생성
첫 번째 행의 뒤집기 여부를 0과 1로 각각 가정
첫 번째 행으로 열 뒤집기 여부 결정
첫 번째 열로 나머지 행 뒤집기 여부 결정
모든 칸 검증
가능한 경우 중 최소 뒤집기 횟수 선택첫 번째 행을 어떻게 뒤집을지만 정하면 나머지 선택이 모두 강제된다는 점을 이용해, 모든 행과 열의 부분집합을 탐색하지 않고 효율적으로 해결하는 것이 핵심이다.
