[프로그래머스] Swift - 2차원 동전 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

2023.10.10 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 최대 10 x 10 크기의 배열 제공
• 열의 각 요소는 0 또는 1로 구성
• 배열을 행 또는 열 단위로 뒤집어서 target과 같은 형태로 만드는 작업 진행
• 이때 target을 만들 수 있는 최소 뒤집기 횟수를 리턴

우선 배열의 뒤집는 경우의 수를 완전 탐색하는 문제는 맞지만 그렇다고 필요 없는 것까지 연산하면 시간 초과가 발생합니다.

즉, 탐색의 범위를 줄여야 합니다.

 

필요 없는 경우

• 같은 열이나 행을 2번 뒤집는 행위

예를 들어 2번째 행을 한번 뒤집었고 3번째 열을 뒤집은 다음 다시 2번째 행을 뒤집는 행위는 의미가 없습니다. 링크

 

이제 각 열과 행은 1번씩만 뒤집는다고 생각하고 구현하면 됩니다.

즉, 각 열과 행 입장에서는 아예 뒤집지 않거나 1번 뒤집히거나 총 2가지 경우가 생깁니다.

5x7 배열이라면 행은 총 2^5개의 경우의 수가 생기고 열은 총 2^7개의 경우가 생기는 것입니다!

 

즉 (2^rowCount) * (2^columnCount) 개의 경우의 수가 생기고 이 것을 완전 탐색하여 target과 같아지는 경우에서의 뒤집기 횟수를 리턴하면 됩니다.

 

각 행 또는 열을 뒤집을지 말지를 정할 때 2진법을 사용하면 편리합니다.

1이면 뒤집기 0이면 가만히 두는 것입니다!

예를 들어5x5 배열일 때 11010 이라면 0,1,3 번째 행만 뒤집는다는 의미입니다.

 

즉, 2진수로 모든 경우의 수를 전부 나타내도록 하고 각각의 경우에서 배열을 뒤집어 보고 target과 같은지 비교하면 완전탐색이 됩니다.

 

이렇게 비트 연산을 통해 해결하는 좋은 답안이 있어서 이번 문제에서는 이 답안(Python)을 Swift로 변환하고 비트 연산을 이용한 풀이를 공부했습니다. 

 

풀이

fileprivate func solution(_ beginning: [[Int]], _ target: [[Int]]) -> Int {
    // 1
    let maxVal = beginning.count * beginning[0].count + 1
    var answer = maxVal

    // 2
    for row in 0..<Int(pow(2, Double(beginning.count))) {
        // 3
        for col in 0..<Int(pow(2, Double(beginning[0].count))) {
            // 4
            let rowConvertCnt = String(row, radix: 2).filter { $0 == "1" }.count
            let colConvertCnt = String(col, radix: 2).filter { $0 == "1" }.count
            // 5
            let cnt = rowConvertCnt + colConvertCnt
            // 6
            if cnt < answer && compare(beginning, target, row, col) {
                answer = cnt
            }
        }
    }

    return answer < maxVal ? answer : -1
}

fileprivate func compare(_ beginning: [[Int]], _ target: [[Int]], _ row: Int, _ col: Int) -> Bool {
    // 7
    for r in 0..<beginning.count {
        // 8
        for c in 0..<beginning[0].count {
            // 9
            let diff = ((row >> r) & 1 + ((col >> c) & 1)) % 2
            // 10
            if (beginning[r][c] + diff) % 2 != target[r][c] {
                return false
            }
        }
    }
    // 11
    return true
}

주석 순서대로 설명을 적겠습니다..!

설명은 5x5 배열을 기준입니다. (다른 크기도 당연히 똑같이 동작합니다!)

1. 앞서 말했 듯이 각 행과 열은 1번씩만 뒤집을 것이기 때문에 최대로 뒤집을 수 있는 횟수를 행과 열의 count로 하고 1을 더하여 target을 완성할 수 없는 경우와 구분합니다.
2. 각 row에서 뒤집는 경우의 수만큼 반복문을 돕니다. 5x5 배열에서는 2^5 개의 경우의 수가 존재합니다.
3. 각 col에서 뒤집는 경우의 수만큼 반복문을 돕니다. 5x5 배열에서는 2^5 개의 경우의 수가 존재합니다.
4. 열과 행의 뒤집기 횟수를 구합니다.
   
   • String(row, radix: 2) 는 각 경우를 2진수로 바꾸어 뒤집기/유지하기를 나타냅니다. 예를 들어 11010이 나오면 1인 위치만 뒤집습니다.
   • String(row, radix: 2).filter { $0 == "1" } 은 1의 개수이기 때문에 뒤집기가 발생한 횟수를 의미합니다.
   • rowConvertCnt와 colConvertCnt는 각각 행 기준으로 뒤집는 횟수와 열 기준으로 뒤집는 횟수를 의미합니다.
5. rowConvertCnt와 colConvertCnt를 더하여 전체 뒤집는 횟수를 구합니다.
6. 기존에 구한 answer보다 작은 횟수인지 검사하고 compare에서 실제로 뒤집어 보아서 target과 같은지 확인합니다.
   • 조건문을 통과하면 우리가 원하는 경우인 것이 때문에 answer를 업데이트합니다.
7. compare 함수는 row와 col의 뒤집는 케이스를 받아와서 실제로 뒤집어서 target과 같은지 파악하는 함수입니다.
8. 2차원 배열의 모든 Element가 target과 같아지는지 비교하기 위해 배열 크기만큼 반복문을 돕니다.
   • r은 행의 인덱스, c 는 열의 인덱스를 의미
9. diff는 해당 위치의 Element에 더할 값입니다.
   • 해당 위치를 뒤집지 않는다면 diff는 0이고 1번 뒤집으면 1이 됩니다. 두번 뒤집으면 2가 되어야 하지만 두번 뒤집는 다는 것은 결국 원상 복구를 의미하기 때문에 % 2 연산을 통해 다시 0으로 만듭니다.
   • row >> r 은 row에서 r 번째 인덱스의 값을 가장 우측 끝으로 이동시키는 비트 연산입니다.
     • row = 10110 이고 r = 2라면 row >> r 의 결과 값은 00101 입니다. 즉, 2번 째 인덱스의 값이 마지막 위치가 되었습니다.
   • (row >> r) & 1 은 '1'과의 and 연산을 통해 가장 우측 비트만을 선택하는 역할을 합니다.
     • 00101과 00001을 and 연산하면 가장 우측 비트인 1만 남는 원리입니다.
   • 즉, (row >> r) & 1 은 row에서 r번째 비트만 구하는 수식입니다. 즉, r번째 인덱스의 행을 뒤집을지 말지를 구할 수 있습니다. (1이면 뒤집기!)
   • (col >> c) & 1 도 마찬가지의 역할입니다. 대신 c 번째 열을 뒤집을지 말지를 구한 것이죠!
   • 이렇게 두 값을 더하고 % 2를 하면 (r, c) 위치의 요소에 더할 값을 구한 것입니다.
10. beginning[r][c]에 diff를 더하여 뒤집어 봅니다. %2를 해서 2번 뒤집는 경우 원상 복구시켜줍니다.
    • target[r][c]와 다르다면 해당 row와 col에서 뒤집는 케이스가 target을 만들 수 없는 것이기 때문에 false를 리턴합니다.
11. 모든 반복문을 통해 2차원 배열의 요소들을 뒤집어 보았고 전부 target과 같은 경우이기 때문에 true를 리턴합니다.

 

이렇게 완전 탐색을 거치면 answer에는 target으로 만들 수 있는 최소 횟수가 담겨있게 됩니다.

만약 answer가 maxVal로 남아 있다면 target을 만들 수 없는 입력값이기 때문에 문제 조건에 따라 -1을 리턴합니다.

 

문제 조건에서 최대 크기의 배열이 10x10이기 때문에,

최악의 경우에서 연산 횟수는 2^10 * 2^10 * 10 * 10 입니다. (마지막 10*10은 compare 함수에서 발생하는 연산)

 

마무리

탐색의 범위를 줄이는 아이디어가 필요했습니다.

열과 행을 1번씩만 뒤집어도 괜찮다는 아이디어로 범위를 줄일 수 있었습니다.

아직 비트 연산을 활용한 문제 풀이에 익숙하지 않았는데 이번에 연습을 해볼 수 있었습니다! (좋은 모범 답안 덕분에~!)