문제 요약
n x m 격자판이 주어진다.
각 칸에는 현재 보이는 값 visible[i][j]와 숨겨진 값 hidden[i][j]가 있다.
한 번의 행동으로 하나의 행 또는 하나의 열 전체를 뒤집을 수 있고, 행동할 때마다 비용 k가 든다.
행과 열을 원하는 만큼 뒤집은 뒤, (1, 1)에서 (n, m)까지 이동한다.
이동 조건은 다음과 같다.
- 상하좌우 인접한 칸으로 이동할 수 있다.
- 같은 칸은 두 번 이상 방문할 수 없다.
- 방문한 칸의 보이는 값을 점수에 더한다.
최종적으로 다음 값을 최대화해야 한다.
방문한 칸의 점수 합 - 뒤집기 비용핵심 아이디어
이 문제는 두 부분으로 나누어 생각할 수 있다.
- 말을 어떤 칸들을 방문하게 할 것인가
- 행과 열을 어떻게 뒤집을 것인가
격자에 적힌 값은 모두 자연수다.
따라서 한 번 방문할 수 있는 칸이라면 방문하는 것이 항상 이득이다.
즉, 경로는 가능한 한 많은 칸을 방문하는 것이 좋다.
경로에서 방문할 수 있는 최대 칸 수
격자 그래프는 체스판처럼 두 색으로 나눌 수 있는 이분 그래프다.
(1, 1)과 (n, m)의 색을 생각하면 다음과 같다.
n과m중 하나라도 홀수라면 모든 칸을 방문하는 경로를 만들 수 있다.n과m이 모두 짝수라면 시작점과 도착점의 색이 같아서 모든 칸을 방문할 수 없다.
따라서 다음과 같이 정리할 수 있다.
n 또는 m이 홀수: 모든 칸 방문 가능
n과 m이 모두 짝수: 색이 다른 칸 하나를 제외하고 방문 가능0-index 기준으로 (0, 0)과 (n - 1, m - 1)은 둘 다 짝수 색이다.
그래서 n, m이 모두 짝수인 경우에는 (i + j) % 2 == 1인 칸 중 하나를 제외한다.
행과 열 뒤집기 상태
어떤 칸 (i, j)의 최종 상태는 다음 값으로 결정된다.
row_flip[i] XOR col_flip[j]- 값이
0이면 현재 보이는 면visible[i][j] - 값이
1이면 숨겨진 면hidden[i][j]
행과 열을 모두 비트마스크로 탐색하면 경우의 수가 너무 커질 수 있다.
그래서 더 작은 축을 비트마스크로 잡는다.
예를 들어 n <= m이면 행 뒤집기 상태를 전부 탐색하고, 각 열은 독립적으로 최선의 선택을 고른다.
반대로 m < n이면 격자를 전치해서 열을 비트마스크 대상으로 바꾼다.
열 선택 최적화
행 뒤집기 상태가 고정되어 있다고 하자.
그러면 각 열은 다음 두 가지 중 하나를 선택하면 된다.
이 열을 뒤집지 않는다.
이 열을 뒤집는다.각 열마다 두 경우의 점수를 계산한 뒤, 더 큰 쪽을 선택한다.
열을 뒤집는 경우에는 비용 k를 빼야 한다.
짝수 x 짝수 격자 처리
n과 m이 모두 짝수라면 모든 칸을 방문할 수 없고, (i + j) % 2 == 1인 칸 하나를 제외해야 한다.
행 상태가 고정되어 있을 때, 어떤 칸 하나를 제외하는 경우도 효율적으로 계산할 수 있다.
먼저 각 열의 최선 점수를 더해 전체 점수를 만든다.
이후 제외할 칸 (i, j)에 대해 다음을 계산한다.
전체 점수 - j열의 기존 최선 점수 + j열에서 (i, j)를 제외했을 때의 최선 점수이렇게 하면 제외할 칸마다 전체 열을 다시 계산하지 않아도 된다.
Python 코드
def solution(visible, hidden, k):
n = len(visible)
m = len(visible[0])
# 더 작은 축을 비트마스크로 탐색하기 위해 필요한 경우 전치한다.
if n <= m:
v = visible
h = hidden
rows, cols = n, m
else:
v = [list(row) for row in zip(*visible)]
h = [list(row) for row in zip(*hidden)]
rows, cols = m, n
need_exclude = (n % 2 == 0 and m % 2 == 0)
answer = -10**30
for mask in range(1 << rows):
row_cost = -k * mask.bit_count()
col_zero = [0] * cols
col_one = [0] * cols
col_best = [0] * cols
for col in range(cols):
score_zero = 0
score_one = -k
for row in range(rows):
row_flipped = (mask >> row) & 1
if row_flipped == 0:
score_zero += v[row][col]
score_one += h[row][col]
else:
score_zero += h[row][col]
score_one += v[row][col]
col_zero[col] = score_zero
col_one[col] = score_one
col_best[col] = max(score_zero, score_one)
total = row_cost + sum(col_best)
if not need_exclude:
answer = max(answer, total)
continue
# n과 m이 모두 짝수라면 0-index 기준 홀수 색 칸 하나를 제외한다.
for row in range(rows):
row_flipped = (mask >> row) & 1
for col in range(cols):
if (row + col) % 2 == 0:
continue
if row_flipped == 0:
value_when_col_zero = v[row][col]
value_when_col_one = h[row][col]
else:
value_when_col_zero = h[row][col]
value_when_col_one = v[row][col]
best_without_cell = max(
col_zero[col] - value_when_col_zero,
col_one[col] - value_when_col_one,
)
candidate = total - col_best[col] + best_without_cell
answer = max(answer, candidate)
return answer코드 설명
작은 축을 비트마스크로 선택
if n <= m:
v = visible
h = hidden
rows, cols = n, m
else:
v = [list(row) for row in zip(*visible)]
h = [list(row) for row in zip(*hidden)]
rows, cols = m, n행과 열은 역할이 대칭이다.
따라서 더 작은 축을 rows로 두고, 2^rows개의 상태만 탐색한다.
행 뒤집기 비용
row_cost = -k * mask.bit_count()mask에서 1인 비트는 뒤집은 행을 의미한다.
뒤집은 행의 개수만큼 비용 k를 뺀다.
열을 뒤집지 않는 경우와 뒤집는 경우
score_zero = 0
score_one = -kscore_zero는 현재 열을 뒤집지 않았을 때의 점수다.
score_one은 현재 열을 뒤집었을 때의 점수다.
열을 뒤집으면 비용이 들기 때문에 처음부터 -k를 반영한다.
칸의 최종 값 결정
row_flipped = (mask >> row) & 1현재 행이 뒤집혔는지 확인한다.
열을 뒤집지 않는 경우와 뒤집는 경우에 따라 최종적으로 보이는 값이 달라진다.
if row_flipped == 0:
score_zero += v[row][col]
score_one += h[row][col]
else:
score_zero += h[row][col]
score_one += v[row][col]행만 뒤집혔거나 열만 뒤집힌 경우에는 숨겨진 값이 보인다.
행과 열을 둘 다 뒤집거나 둘 다 뒤집지 않은 경우에는 현재 보이는 값이 유지된다.
짝수 x 짝수에서 한 칸 제외
if (row + col) % 2 == 0:
continue시작점과 도착점은 0-index 기준 짝수 색이다.
n과 m이 모두 짝수라면 반대 색 칸 하나를 제외해야 하므로 (row + col) % 2 == 1인 칸만 제외 후보가 된다.
candidate = total - col_best[col] + best_without_cell전체 점수에서 해당 열의 기존 최선 점수를 빼고, 해당 칸을 제외했을 때의 열 최선 점수를 더한다.
시간 복잡도
작은 축의 길이를 s = min(n, m), 큰 축의 길이를 l = max(n, m)이라고 하자.
각 비트마스크 상태마다 전체 격자를 한 번 확인한다.
O(2^s * n * m)따라서 이 풀이는 작은 축의 길이가 비교적 작을 때 효과적이다.
공간 복잡도
열마다 계산한 점수를 저장하는 배열을 사용한다.
O(max(n, m))전치가 필요한 경우에는 입력 크기만큼의 추가 공간이 사용될 수 있다.
정리
이 문제의 핵심은 다음 세 가지다.
- 모든 값이 자연수이므로 가능한 한 많은 칸을 방문하는 경로가 유리하다.
n,m이 모두 짝수인 경우에만 한 칸을 제외해야 한다.- 행 상태를 고정하면 각 열의 뒤집기 여부는 독립적으로 최적화할 수 있다.
경로 문제처럼 보이지만, 실제로는 격자의 parity와 행/열 뒤집기 상태를 이용해 최적화 문제로 바꾸는 것이 핵심이다.
