문제
- RxC 직사각형 모양의 각 칸에 앞, 뒤가 구분되는 동전이 놓여있다. 초기 상태와 목표 상태가 주어졌을 때, 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 리턴하기.
- 동전을 뒤집는다는 것은 같은 줄 또는 같은 열의 모든 동전을 한 번에 뒤집는 것이다.
- 목표 상태를 만들지 못하는 경우 -1 리턴하기
풀이 1
- 두 번 뒤집으면 그대로이므로 한 번만 뒤집는 것이 최소 횟수가 된다.
- 각 행의 첫 번째가 목표 상태와 다른 경우 전부 뒤집은 다음, 각 열이 0 또는 1로만 이루어져 있으면 목표 상태로 만들 수 있다는 의미다.
- 시간 복잡도
- board 만들기 / 행 뒤집기 / 열 확인 모두 $O(RC)$ 에 해당하고 최대 100번의 연산이므로 충분히 가능하다.
def solution(beginning, target):
# beginning과 target 차이
# 뒤집어야 하면 1, 그대로 둬야하면 0
row, col = len(beginning), len(beginning[0])
board = [[1 if beginning[i][j] != target[i][j] else 0 for j in range(col)] for i in range(row)]
answer = 0
# 행 전부 뒤집기
for i in range(row):
if board[i][0] == 1:
answer += 1
for j in range(col):
board[i][j] = 1 - board[i][j]
# 열 확인하기
for j in range(col):
tmp = set([ board[i][j] for i in range(row)]) # j열
if len(tmp) == 2: # 0과 1이 섞여 있다면
answer = -1 목표 상태 도달 불가능
break
elif 1 in tmp : # 1로만 이루어져 있으면 = 뒤집어야 하면
answer += 1
return answer
2, 4, 6, 9 번 실패
열 뒤집은 뒤 행 확인하는 것으로 하면 3, 4, 6 실패
풀이 2
- 행 -> 열 또는 열 -> 행 순서대로 뒤집으면 안되는 예외 사항이 있다는 소리다.
- 행을 뒤집지 말고 넘어가야 할 수도 있다! 각 행별로 뒤집어야 하는 경우와 뒤집지 말아야 하는 경우를 모두 확인해야 한다.
- 시간 복잡도
- 행이 n개일 때, 뒤집지 않은 경우와 뒤집는 경우가 있으므로 총 $2^n$개의 경우의 수가 존재하게 된다.
answer = float('inf')
# 행 뒤집기
def flip(ary, row, col):
for j in range(col) :
ary[row][j] = 1 - ary[row][j]
# 각각의 열이 0 또는 1로만 이루어져 있는지 확인하기
def check(ary, row, col):
cnt = 0
for j in range(col):
tmp = set([ ary[i][j] for i in range(row)]) # j 열
if len(tmp) == 2 : # 0과 1이 섞여있는 경우
return -1 # 목표 상태로의 도달 불가능
elif 1 in tmp: # 1로만 이루어진 경우 = 뒤집어야 하는 경우
cnt += 1
return cnt
def dfs(ary, depth, cnt, row, col):
global answer
# 모든 행 확인한 경우
if depth == row :
# 열 확인하기
ret = check(ary, row, col)
if ret >= 0 :
answer = min(answer, cnt+ret) # 최솟값 저장하기
return
dfs(ary, depth+1, cnt, row, col) # 행을 뒤집지 않는 선택
flip(ary, depth, col)
dfs(ary, depth+1, cnt+1, row, col) # 행을 뒤집는 선택
flip(ary, depth, col)
def solution(beginning, target):
row, col = len(beginning), len(beginning[0])
# beginning과 target 차이
# 뒤집어야 하면 1, 그대로 둬야하면 0
board = [[1 if beginning[i][j] != target[i][j] else 0 for j in range(col)] for i in range(row)]
dfs(board, 0, 0, row, col)
if answer == float('inf') :
return -1
return answer
풀이 3
- 비트마스크를 통해서도 모든 경우의 수를 확인할 수 있다.
- 00...0 ~ 11...1 까지 1일 때 각 행을 뒤집는다고 생각하기
- 해당 경우의 수에 따라 행을 뒤집고 열을 뒤집어 목표 상태 도달할 수 있는지 확인하기!
# 행 뒤집기
def flip(ary, bits, row):
row_cnt = 0
for i in range(row):
if bits & (1 << i): # i번째 행을 뒤집어야 하는 경우
ary[i] = [1-e for e in ary[i]]
row_cnt += 1
return ary, row_cnt
# 열 확인하기
def check(ary, col):
col_cnt = 0
for j in range(col):
tmp = set([row[j] for row in ary]) # j열
if len(tmp) == 2: # 목표 상태 도달 불가능
return -1
elif 1 in tmp : # 뒤집어야 하는 경우
col_cnt += 1
return col_cnt
def solution(beginning, target):
answer = float('inf')
row, col = len(beginning), len(beginning[0])
board = [[1 if beginning[i][j] != target[i][j] else 0 for j in range(col)] for i in range(row)]
# 0...0 : 모든 행을 뒤집지 않는다
# 1...1 : 모든 행을 뒤집는다
for bits in range(2**row):
flipped, row_cnt = flip(board[:], bits, row) # 뒤집어야 할 행만큼 행 뒤집기
col_cnt = check(flipped, col) # 열 확인하기
if col_cnt == -1 : # 목표 상태로 도달 불가능
continue
answer = min(row_cnt+col_cnt, answer)
if answer == float('inf'):
return -1
return answer
References
