한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.
예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.
직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.
내가 시도한 풀이법의 경우, 극단적인 테스트 케이스(행 == 열 == 10이며 많은 뒤집기 횟수가 필요한 경우)일 경우 시간 초과의 위험성이 있다. 따라서 문제를 더 확장할 경우 반쪽짜리 정답이라고 생각된다.
이차원 배열을 뒤집는 경우의 수는 언뜻 보면 무한히 많아보이지만, 다음과 같은 특징들 때문에 2^(행의 크기 + 열의 크기)로 한정된다.
뒤집는 순서는 상관이 없다. 예를 들어 2열 -> 4행 순으로 뒤집던, 4행 -> 2열 순으로 뒤집던 그 결과는 동일하다.
2차원 배열의 각 원소는 두 가지 상태를 가지므로, 원소 하나를 기준으로 최대 1번의 뒤집기가 유효하다. 또한 원소 하나에 영향을 미치는 뒤집기는 그 행과 그 열의 총 2번이다.
따라서 1, 2에 의해, 행의 크기와 열의 크기만큼 뒤집을지, 뒤집지 않을 지의 두 가지 경우를 고려해 주면 된다. 문제의 조건에 따라 이는 2^20, 약 백만 번의 연산을 통해 모든 경우의 수를 테스트 해 볼 수 있다. 구체적인 알고리즘은 다음과 같다 :
테스트 케이스 리스트를 만들고, 이를 count 수에 따라 sort한다(sort하지 않으면 시간 초과가 나옴을 확인했다)
각 테스트 케이스에 따라 초기 배열을 뒤집는다.
계산을 빠르게 하기 위해 비트마스킹 방법을 이용했다. beginning과 target의 각 행을 비트로 취급하여 정수로 바꾸었다. 행을 뒤집을 때는 (2^행의 크기) - 1 에서 그 정수를 빼면 되고, 열을 뒤집을 때는 각 정수에 대해 (2^뒤집고자 하는 열의 숫자)를 xor 연산을 치루면 된다.
만약 뒤집은 결과물이 target 리스트와 같다면 현재 뒤집은 횟수를 반환한다.
탐색이 실패하면 -1을 반환한다.
풀이 코드는 다음과 같다 :
풀이 코드
def make_list(lst, row, col) :
result = list()
for i in range(row) :
result.append(sum([(1 << j) * lst[i][j] for j in range(col)]))
return result
def flip(lst, flip_chk, row, col) :
length = len(lst)
result = list()
for i in range(row) :
if flip_chk & (1 << i) :
result.append((1 << col) - lst[i] - 1)
else :
result.append(lst[i])
for i in range(col) :
if flip_chk & (1 << (row + i)) :
for j in range(row) :
result[j] ^= (1 << i)
return result
def solution(beginning, target):
row, col = len(beginning), len(beginning[0])
beginning_list = make_list(beginning, row, col)
target_list = make_list(target, row, col)
test_case = list(range(1 << (row + col)))
test_case.sort(key = lambda x : bin(x).count('1'))
for i in test_case :
fliped_list = flip(beginning_list, i, row, col)
cnt = bin(i).count('1')
if fliped_list == target_list :
return cnt
return -1
그리고, 다른 분이 풀이하셨던 위 방법보다 더 빠른 풀이를 발견하였기에 서술한다.
beginning과 target의 각 원소에 대해 xor 연산을 수행한다. 그 결과가 0이라면 뒤집는 횟수가 짝수(0), 1이라면 뒤집는 횟수가 홀수(1)가 된다. 즉 이 '목표와의 차이값' 시점으로 문제를 풀이한다. 만약 모든 값이 0이라면
이 xor의 첫번째 행과 나머지 행을 기준으로, 일치하지 않는 행을 뒤집는다. 뒤집은 결과마저 첫번째 행과 동일하지 않다면 어떤 방식으로든 정답을 얻을 수 없다는 의미이므로 -1을 반환한다.
위 2번까지의 결과물의 열을 기준으로 보면, 0으로 이루어졌거나 또는 1로 이루어져있음을 알 수 있다. 이 때 1로 이루어진 열의 개수를 센다.
2번에서 뒤집은 횟수 + 3번에서 센 횟수가 정답 해 중 하나가 된다. 또한, 반대로 첫 번째 행을 뒤집는다는 가정 하에 하나의 해를 더 얻을 수 있다. 이 경우의 해는 (행의 크기 - 2번에서 뒤집은 횟수) + (열의 크기 - 3번에서 센 횟수) 가 된다. 둘 중 더 작은 값을 출력해주면 된다.
이 방법은 훨씬 더 코드도 간결하고 계산 속도도 빠르다. 아직 구현해보진 않았지만, 좋은 풀이기에 남겨 둔다.
