[JS] 2차원 동전 뒤집기

동전뒤집기 문제에서 생각할 점은 어느 칸이던 같은 줄을 2번이상 뒤집는건 의미가 없다는 것이다.

 

즉 , 가로 1~10 세로 1~10 까지 있다고 가정한다면 

 

가로 3번째 라인을 1번뒤집나 3번뒤집나 5번 뒤집나 해당 라인의 결과는 같게 된다.

 

따라서 모든 라인의 줄을 최대 1번까지만 뒤집을 수 있다고 생각할 수 있다.

 

 

그다음으로 생각해야 할점은 순서가 상관이 없다는 것이다.

 

가로 3번 -> 세로2번 -> 가로 6번 이런식으로 뒤집나

세로 2번 -> 가로 6번 -> 가로3번 이런식으로 뒤집나 결과가 같게 나온다.

 

 

 

즉 위 문제는 2^10으로 나오는 완전탐색을 할 필요가 없다! 10번의 경우만 체크하면 된다.

 

 

 

1. 우선 문제를 조금 간략화 하기 위해서 beginning과 target 배열을 비교해서 같으면 false 다르면 true로 반환한다.

위 과정을 통해서 beginning을 target으로 만드는 문제가 아닌, 배열을 false로 만들면 되는 문제로 변하였다.

 

2. 먼저 세로줄의 맨 위칸을 모두 false로 만들어주게 세로줄을 바꿔준다.

3. 그 이후 가로줄의 첫 열을 모두 false로 만들어주게 가로줄을 바꿔준다.

 

2-3 번과정을 거치면서 바꿔야 할 점을 모두 찾을 수 있다.

 

하지만 이 경우 예외케이스가 2가지 더 발생하게 된다.

 

첫열 첫행 즉 [0][0]에 해당하는 부분이 2번 바뀌어야 할때 방금과 같은 로직으로는 무조건 행부터 바꾸기 때문에 예외가 생길 수 있다. 따라서 열부터도 검사를 해주는 과정이 필요하다.

 

단, 해당 부분이 2번바뀌어야 할때 행-> 열 열-> 행 2가지 케이스를 검사를 해주어야 하므로 총 케이스는 3가지가 나오게 된다.

 

 

 

약간 구조화를 마지막에 잘 못한 문제인 같아 접근은 잘 이해했는데 해결이 아쉬운 문제였다.

 

function solution(beginning, target) {
    let map = [...Array(beginning.length)].map(_ => Array(beginning[0].length).fill(false))
    const rLen = beginning.length
    const cLen = beginning[0].length
    
    const clearMap = () => {
        for (let i = 0 ; i < rLen ; i++){
            for (let j = 0 ; j< cLen ;j++){
                if (beginning[i][j]!==target[i][j]) map[i][j] = true
                else map[i][j] = false
            }
        }
    }
    
    
    const changeRow = (n) => {
        for (let i = 0 ; i < cLen ; i++) map[n][i] = !map[n][i]
    }
    const changeCol = (n) => {
        for (let i = 0 ; i < rLen ; i++) map[i][n] = !map[i][n]
    }
    
    const reverseCol = (ret) => {
        for (let i = 0 ; i < cLen ; i++){
            if (map[0][i]) {
                changeCol(i)
                ret ++
            }
        }
        return ret
    }
    
    const reverseRow = (ret) => {
        for (let i = 0 ; i < rLen ; i++){
            if(map[i][0]) {
                changeRow(i)
                ret ++
            }
        }
        return ret
    }
    
    
    let ret = []
    
    clearMap()
    let tmp = 0
    tmp = reverseCol(tmp)
    tmp = reverseRow(tmp)
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(map[i][j]) return -1
        }
    }
    ret.push(tmp)
    
    clearMap()
    tmp = 1
    changeCol(0)
    tmp = reverseRow(tmp)
    tmp = reverseCol(tmp)
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(map[i][j]) return -1
        }
    }
    ret.push(tmp)
    
    clearMap()
    tmp = 1
    changeRow(0)
    tmp = reverseCol(tmp)
    tmp = reverseRow(tmp)
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(map[i][j]) return -1
        }
    }
    ret.push(tmp)
    
    clearMap()
    let cRet = 1
    changeCol(0)
    cRet = reverseRow(cRet)
    cRet = reverseCol(cRet)
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(map[i][j]) return -1
        }
    }
    
    return Math.min(...ret)
}