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

프로그래머스

 

📄 문제

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.

 

예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

 

📝 풀이

 

오답 코드

• 두개의 반례를 찾아내지 못하여 결국 처음부터 다시 작성하기로 하였습니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void flip(vector<vector<int>>& map, int pos, bool isHorizontal)
{
    if(isHorizontal)
        for(int i = 0; i < map[0].size(); ++i)
            map[pos][i] = map[pos][i] ? 0 : 1;
    else
        for(int i = 0; i < map.size(); ++i)
            map[i][pos] = map[i][pos] ? 0 : 1;
}

bool print(vector<vector<int>>& map)
{
    for(int i = 0; i < map.size(); ++i)
    {
        for(int j = 0; j < map[0].size(); ++j)
            printf("%d ", map[i][j]);
        cout<<endl;
    }
    
    cout<<endl;
       
    return true;
}

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

bool checkMap(vector<vector<int>> beginning, vector<vector<int>> target)
{
    int row = beginning.size();
    int col = beginning[0].size();
    
    if(row < 2 || col < 2)
        return false;
    
    bool checkCol = true;
    for(int i = 0; i < row; ++i)
        for(int j = 0; j < col - 1; ++j)
        {
            if(beginning[i][j] != beginning[i][j + 1] || target[i][j] != target[i][j + 1])
                checkCol = false;
        }
    
    bool checkRow = true;  
    for(int i = 0; i < col; ++i)
        for(int j = 0; j < row - 1; ++j)
        {
            if(beginning[j][i] != beginning[j + 1][i] || target[j][i] != target[j + 1][i])
                checkRow = false;
        }    
    
    if(checkCol || checkRow)
        printf("TRUE");
    
    return checkCol || checkRow;
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    if(compare(beginning, target))
        return 0;

    vector<vector<int>> original = beginning;
    
    int row = beginning.size();
    int col = beginning[0].size();
    bool isSame = checkMap(beginning, target);
    
    if(min(row, col) == 1 || isSame)
    {
        if(isSame)
            row = row < col ? 1 : row;
        
        if(row == 1)
        {
            int diff = 0;
            for(int i = 0; i < col; ++i)
                if(beginning[0][i] != target[0][i])
                    ++diff;
            
            printf("ROW %d", diff);
            
            int answer = diff < col / 2 ? diff : col - diff + 1;
            if(isSame)
                answer += beginning.size() - 1;
            
            return answer;                 
        }
        else
        {
            int diff = 0;
            for(int i = 0; i < row; ++i)
                if(beginning[i][0] != target[i][0])
                    ++diff;
            
            printf("COL %d", diff);
            
            int answer = diff < row / 2 ? diff : row - diff + 1;
            if(isSame)
                answer += beginning[0].size() - 1;
            
            return answer;            
        }
    }
    
    int answer1 = 0;
    bool escape1 = false;
    bool success1 = false;
    for(int i = 0; i < row; ++i)
        if(beginning[i][0] != target[i][0])
        {
            ++answer1;
            flip(beginning, i, true);
            if(compare(beginning, target))
            {
                escape1 = true;
                success1 = true;
                break;   
            }
        }
    if(!escape1)
    for(int i = 0; i < col; ++i)
        if(beginning[0][i] != target[0][i])
        {
            ++answer1;
            flip(beginning, i, false);
            if(compare(beginning, target))
            {
                success1 = true;
                break;
            }
        }
    if(!success1)
        answer1 = -1;
    
    int answer2 = 0;
    bool escape2 = false;
    bool success2 = false;
    beginning = original;
    for(int i = 0; i < col; ++i)
        if(beginning[0][i] != target[0][i])
        {
            ++answer2;
            flip(beginning, i, false);
            if(compare(beginning, target))
            {
                escape2 = true;
                success2 = true;
                break;   
            }
        }      
    if(!escape2)
    for(int i = 0; i < row; ++i)
        if(beginning[i][0] != target[i][0])
        {
            ++answer2;
            flip(beginning, i, true);
            if(compare(beginning, target))
            {
                success2 = true;
                break;             
            }
        }
    if(!success2)
        answer2 = -1;
  
    return min(answer1, answer2);
}

 

 

정답 코드

#include <vector>
#include <algorithm>

using namespace std;

void flip(vector<vector<int>>& map, int pos, bool isHorizontal)
{
    if(isHorizontal)
        for(int i = 0; i < map[0].size(); ++i)
            map[pos][i] = map[pos][i] ? 0 : 1;
    else
        for(int i = 0; i < map.size(); ++i)
            map[i][pos] = map[i][pos] ? 0 : 1;
}

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

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {

    int row = beginning.size();
    int col = beginning[0].size();
    
    // 행 -> 열 순서에서 행이 다른경우? flip
    int answer1 = 0;
    bool escape1 = false;
    bool success1 = false;
    vector<vector<int>> ch = beginning;
    for(int i = 0; i < row; ++i)
        if(ch[i][0] != target[i][0])
        {
            ++answer1;
            flip(ch, i, true);
            if(compare(ch, target))
            {
                escape1 = true;
                success1 = true;
                break;   
            }
        }
    if(!escape1)
    for(int i = 0; i < col; ++i)
        if(ch[0][i] != target[0][i])
        {
            ++answer1;
            flip(ch, i, false);
            if(compare(ch, target))
            {
                success1 = true;
                break;
            }
        }
    if(!success1)
        answer1 = -1;
    
    // 열 -> 행 순서에서 열이 다른경우? flip
    int answer2 = 0;
    bool escape2 = false;
    bool success2 = false;
    ch = beginning;
    for(int i = 0; i < col; ++i)
        if(ch[0][i] != target[0][i])
        {
            ++answer2;
            flip(ch, i, false);
            if(compare(ch, target))
            {
                escape2 = true;
                success2 = true;
                break;   
            }
        }      
    if(!escape2)
    for(int i = 0; i < row; ++i)
        if(ch[i][0] != target[i][0])
        {
            ++answer2;
            flip(ch, i, true);
            if(compare(ch, target))
            {
                success2 = true;
                break;             
            }
        }
    if(!success2)
        answer2 = -1;
    
    // 행 -> 열 순서에서 행이 같은경우? flip
    int answer3 = 0;
    bool escape3 = false;
    bool success3 = false;
    ch = beginning;    
    for(int i = 0; i < row; ++i)
        if(ch[i][0] == target[i][0])
        {
            ++answer3;
            flip(ch, i, true);
            if(compare(ch, target))
            {
                escape3 = true;
                success3 = true;
                break;   
            }
        }
    if(!escape3)
    for(int i = 0; i < col; ++i)
        if(ch[0][i] != target[0][i])
        {
            ++answer3;
            flip(ch, i, false);
            if(compare(ch, target))
            {
                success3 = true;
                break;
            }
        }
    if(!success3)
        answer3 = -1;    
    
    // 열 -> 행 순서에서 열이 같은경우? flip
    int answer4 = 0;
    bool escape4 = false;
    bool success4 = false;
    ch = beginning;    
    for(int i = 0; i < col; ++i)
        if(ch[0][i] == target[0][i])
        {
            ++answer4;
            flip(ch, i, false);
            if(compare(ch, target))
            {
                escape4 = true;
                success4 = true;
                break;   
            }
        }   
    if(!escape4)
    for(int i = 0; i < row; ++i)
        if(ch[i][0] != target[i][0])
        {
            ++answer4;
            flip(ch, i, true);
            if(compare(ch, target))
            {
                success4 = true;
                break;             
            }
        }
    if(!success4)
        answer4 = -1;      
    
    return min({answer1, answer2, answer3, answer4});
}

• 네가지의 규칙을 적용하여 문제를 해결합니다.
  • 행을 먼저 검사하여 행의 맨 앞의 값이 서로 다르다면 flip을 하고 열의 맨 앞 값이 다르다면 flip을 한 갯수
  • 열을 먼저 검사하여 열의 맨 앞의 값이 서로 다르다면 flip을 하고 행의 맨 앞 값이 다르다면 flip을 한 갯수
  • 행을 먼저 검사하여 행의 맨 앞의 값이 서로 같다면 flip을 하고 열의 맨 앞 값이 다르다면 flip을 한 갯수
  • 열을 먼저 검사하여 열의 맨 앞의 값이 서로 같다면 flip을 하고 행의 맨 앞 값이 다르다면 flip을 한 갯수
• 위에서 구한 네가지의 정답(answer1, 2, 3, 4)의 최소값을 리턴합니다.