[programmers] 2차원 동전 뒤집기

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

가지치기를 적용한 dfs / 백트래킹

 

---------------------------------------------------풀이----------------------------------------------------

 

dfs()함수의 구조는 단순하다.

1. 현재 뒤집은 상태가 target과 일치하면 현재 cost를 answer값과 비교 후 종료.

2. 일치하지 않으면 각 rows와 columns에서 뒤집지 않은(!visited[]) row나 column 중 target과 다른 부분이 있으면 뒤집고 dfs()를 호출하고, 다시 복구한다.

 

여기서 두 가지 가지치기를 적용하였다.

1. 현재 cost가 이미 answer값 이상이면 종료한다.

2. 매번 모든 row와 column을 검사하는 것이 아니라, 이미 검사한 부분 이후부터 검사할 수 있도록 row와 col 값을 매개변수로 넘긴다.

#include <string>
#include <vector>
#include <limits.h>

using namespace std;

bool visited_rows[11] = {0, };
bool visited_cols[11] = {0, };
vector<vector<int>> map, target;
int answer;

bool is_target(){
    for(int i = 0; i < map.size(); i++){
        for(int j = 0; j < map[i].size(); j++){
            if(map[i][j] != target[i][j])
                return false;
        }
    }
    return true;
}

bool is_row_diff(int r){
    for(int i = 0; i < map[r].size(); i++){
        if(map[r][i] != target[r][i]){
            return true;
        }
    }
    return false;
}

bool is_col_diff(int c){
    for(int i = 0; i < map.size(); i++){
        if(map[i][c] != target[i][c]){
            return true;
        }
    }
    return false;
}

// mode가 0이면 n번째 row, 1이면 n번째 col 뒤집기
void reverse_coins(int n, int mode){
    if(mode == 0){
        for(int i = 0; i < map[n].size(); i++){
            map[n][i] ^= 1;
        }
    }
    else{
        for(int i = 0; i < map.size(); i++){
            map[i][n] ^= 1;
        }
    }
}

// 체크한 row와 col
void dfs(int cost, int row, int col){
    if(cost >= answer){
        return;
    }
    // target과 동일해졌으면 최소 횟수를 구해 answer와 비교
    if(is_target()){
        if(answer > cost){
            answer = cost;
        }
        return;
    }
    
    // 각 row와 col을 돌면서 서로 다른게 위치한 곳이 있으면 동전 뒤집기.
    for(int i = row; i < map.size(); i++){
        // row에 다른게 있으면 row 뒤집기
        if(!visited_rows[i] && is_row_diff(i)){
            reverse_coins(i, 0);
            visited_rows[i] = true;
            dfs(cost + 1, i, col);
            reverse_coins(i, 0);
            visited_rows[i] = false;
        }
    }
    for(int i = col; i < map[0].size(); i++){
        // col에 다른게 있으면 col 뒤집기
        if(!visited_cols[i] && is_col_diff(i)){
            reverse_coins(i, 1);
            visited_cols[i] = true;
            dfs(cost + 1, row, i);
            reverse_coins(i, 1);
            visited_cols[i] = false;
        }
    }
}

// 같은 줄에 있는 모든 동전 뒤집어야 함.
// 초기 상태에서 목표 상태까지 가기 위해 뒤집는 최소 횟수=?
// 불가능하면 -1.
int solution(vector<vector<int>> beginning, vector<vector<int>> _target) {
    answer = INT_MAX;
    map = beginning;
    target = _target;
    dfs(0, 0, 0);
    if(answer == INT_MAX){
        answer = -1;
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음 단순하게 dfs로 풀었더니, 역시나 시간초과가 나는 테스트케이스가 많았다. 이 때의 점수는 42.9/100

1~21의 테스트케이스 중 2,8,9,15,16,17,19,20,21만 통과하였다.

따라서 dp를 적용한 방법을 생각해보게 되었으나, 도저히 떠오르지 않았다.

그러던 중, 이미 검사한 row와 col에 대해서는 더이상 체크할 필요가 없다는 사실을 깨달았다.

이미 뒤집었거나 뒤집지 않도록 결정내린 row와 col은 검사할 필요가 없다.

어차피 최솟값은 각 row와 col에 대해 한 번만 뒤집어 나와야하기 때문이다.

따라서 이 방식으로 가지치기를 해주었고, 모든 테스트케이스를 통과할 수 있었다.