2차원 동전 뒤집기 [자바]

 

🧫 문제 분석

✔️ 출처

2차원 동전 뒤집기 level 3

📖 문제

 

DFS 로 풀었지만 정석은 bitmask인듯하다. 

행 기준으로 현재 행을 뒤집는 경우와 뒤집지 않는 경우를 탐색하여 뒤집는 행을 갖는 조합을 만들고 

열 기준으로도  조합을 만들어서

 

최종적으로 조합을 적용해 동전들을 뒤집고, target과 비교해서 맞다면 

뒤집기 카운트와 비교해서 최솟값을 찾는다. 

 

 

이문제를 풀면서

행과 열을 왔다갔다하면서 뒤집어야 나올 수 있는 target이 있을 줄 알았는데 

그게 아니였다.

 

궁금해서 gpt 에게 물어봤다.

begin[i][j] ^ R[i] ^ C[j] == target[i][j]

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    
    static int[][] otarget;
    static int answer = Integer.MAX_VALUE;
    static int size;
    static int row, col;
    
    public int solution(int[][] beginning, int[][] target) {
        row = target.length;
        col = target[0].length;
        size = row * col;
        otarget = target;
        
        dfs2(beginning, 0, 0);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    private void dfs2(int[][] map, int cnt, int depth) {
        if (cnt >= answer) return;
        if (depth == row + col) {
            if (valid(map)) answer = Math.min(answer, cnt);
            return;
        }

        // 행 부분 탐색
        if (depth < row) {
            // 뒤집지 않음
            dfs2(map, cnt, depth + 1);
            // 해당 행 뒤집음
            int[][] newMap = cloneMap(map);
            switching(newMap, depth, true);
            dfs2(newMap, cnt + 1, depth + 1);
        } 
        // 열 부분 탐색
        else {
            int idx = depth - row;
            // 뒤집지 않음
            dfs2(map, cnt, depth + 1);
            // 해당 열 뒤집음
            int[][] newMap = cloneMap(map);
            switching(newMap, idx, false);
            dfs2(newMap, cnt + 1, depth + 1);
        }
    }
    
    private boolean valid(int[][] map) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] != otarget[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private int[][] cloneMap(int[][] map) {
        int[][] tmp = new int[row][col];
        for (int i = 0; i < row; i++) {
            tmp[i] = map[i].clone();
        }
        
        return tmp;
    }
    
    private void switching(int[][] tmp, int line, boolean isRow) {
        
        for (int i = 0; i < (isRow ? col : row); i++) {
            // 한 행을 바꿈
            if (isRow) {
                tmp[line][i] = (tmp[line][i] + 1) % 2;
                
                // 한 열을 바꿈
            } else {
                tmp[i][line] = (tmp[i][line] + 1) % 2;
            }
        }
        
    }
}

 

 

❗ 오답노트 / 필요한 지식

1. 항상 느끼지만 자꾸 하나씩 놓친다 .. 답답하다.