코딩테스트 -- 2차원 동전 뒤집기 - (프로그래머스 / C++)

 

 

프로그래머스

 

 

문제 요약

---

직사각형의 판위에 동전을 가지런히 나열하여 놓여져 있는 상태에서 동전을 뒤집는 놀이를 한다고 합니다.

 

이상태에서 동전을 한번 뒤집을때 행과 열의 돌들을 모두 뒤집어야하는 게임이라고합니다. 

 

여기서 저희가 구해야 하는것은

목표상태를 최소의 뒤집기 횟수로 도달하는가, 그리고 최소횟수는 얼마인가 하는것입니다!

 

---

 

 

이전 글에서 풀었던 고고학 문제와 약간 비슷한 류인것 같았습니다. 

똑같이 판에서 게임을 진행하고 동전을 뒤집을때 마다 다음 경우의 수가 한정되는듯 보였습니다. 

 

 

 

동전을 뒤집을 경우 행과 열이 같이 뒤집히게됩니다. 

그렇다면 하나의 동전을 뒤집을때

1. 행을 다 뒤집는다

2. 열을 다 뒤집는다

3. 뒤집지 않는다.

4. 둘다 뒤집는다

 

이렇게 4가지의 경우가 생깁니다. 

 

 

그런데 여기서

만약 1번째 행을 필요에 따라 한번 뒤집었을 경우 그 행에서 행의 뒤집힘이 일어날수 있을까 하는 의문이 들었습니다. 

 

정답은 뒤집을 필요 없다 입니다. 

 

동전은 앞과 뒤 2개의 경우로 나뉘어져있는데,

첫번째 칸에서 동전을 뒤집기 위해 행을 뒤집었다고 가정했을때

그 행을 다시 뒤집으면 다시 원상태로 돌아가기 때문에

 

그 행에 대해 한번이라도 뒤집었다면 그 행에 대해서는 생각할 필요가 없다는 것을 알 수 있습니다.

 

 

한 행에서 회전이 이루어졌다면 그 행은 더이상 생각할 필요가 없다!

여기서 알 수 있는 점은 각 행당 한번, 그리고 각 열당 한번씩만 체크해주고 목표상태에 도달했는지만 확인해주면 끝!

 

만약 아래와 같은 사각형 판이 나온다면 각 칸에 맞게 뒤집어 주면 끝... 

 

 

 

 

이제 이 경우를 생각하여 경우에 대한 탐색을 진행해주면 끝!

 

 

 

 

그럼 이제 코드 시작!

---

 

코드 자체는 매우 직관적입니다.

 

 

가장 먼저 필요한 변수들을 저장해주고

int answer = 987654321;
int y_size = 0;
int x_size = 0;


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

    y_size = beginning.size();
    x_size = beginning[0].size();

    find(0,0,0, target, beginning);

    if (answer == 987654321) {
        answer = -1;
    }
    
    return answer;
}

 

 

탐색함수에서 예외 사항을 검사하도록 설계해줍시다.

void find(int y,int x, int count, vector<vector<int>>& target, vector<vector<int>> beginning) {
    int calAns = 987654321;
    
    if (x == x_size) { // 행끝
        if (y == y_size - 1) { // 탐색 끝
            if (target == beginning) {
                answer=min(answer, count);
            }
            return;
        }
        else {
            x = 0;
            y += 1;
        }
    }

 

 

그리고 경우에 대한 탐색을 실행해 줍시다.

if (x == 0 && y==0) { // 가로세로회전 가능 
        //1. 가로
        rotation(y, x, 1, beginning);
        find(y, x + 1, count + 1, target, beginning);
        rotation(y, x, 1, beginning);

        //2. 세로회전
        rotation(y, x, 2, beginning);
        find(y, x + 1, count + 1, target, beginning);
        rotation(y, x, 2, beginning);

        //3. 회전 x
        find(y, x + 1, count, target, beginning);

        // 4. 둘다 회전
        rotation(y, x, 3, beginning);
        find(y, x + 1, count + 2, target, beginning);
        rotation(y, x, 3, beginning);
    }
    else if (y == 0) { // 세로회전만 고려
        rotation(y, x, 2, beginning);
        find(y, x + 1, count + 1, target, beginning);
        rotation(y, x, 2, beginning);

        find(y, x + 1, count, target, beginning);
    }
    else if(x==0) { // 가로회전만
        rotation(y, x, 1, beginning);
        find(y, x + 1, count + 1, target, beginning);
        rotation(y, x, 1, beginning);

        find(y, x + 1, count, target, beginning);
    }
    else { // 회전 못해  >> 맞는지 확인하고 아니면 중지?
        if (target[y][x] != beginning[y][x]) {
            return;
        }
        else {

            find(y, x + 1, count, target, beginning);
        }
    }

모든 경우에 대해서 고려하는 부분에서 코드가 많이 길어졌습니다..

 

 

 

 

 

다음은 rotation함수! 

아래처럼 행과 열을 회전시키는 함수를 구성해주면

void rotation(int y, int x, int way,vector<vector<int>>& beginning) { // 1. 가로 , 2. 세로, 3. 둘다
    if (way == 1) {// 가로
        for (auto& v : beginning[y])
        {
            if (v == 0) {
                v = 1;
            }
            else {
                v = 0;
            }
        }
    }
    else if (way == 2) { // 세로
        for (auto& v : beginning)
        {
            if (v[x] == 0) {
                v[x] = 1;
            }
            else {
                v[x] = 0;
            }
        }
    }
    else { // 둘다
        for (auto& v : beginning[y])
        {
            if (v == 0) {
                v = 1;
            }
            else {
                v = 0;
            }
        }

        for (auto& v : beginning)
        {
            if (v[x] == 0) {
                v[x] = 1;
            }
            else {
                v[x] = 0;
            }
        }
    }
}

 

 

끝!

 

 

 

여기까지 코드를 작성하고 정답처리도 받았지만 위의 코드에서 약간 더 수정이 가능할 것으로 보였습니다...

(코드가 너무 길어져버렸네.... 탐색에서 벡터를 받아가는 부분도 최적화 가능해보임)

 

 

그리고 다른 분들의 코드들을 찾아보니 위의 방법과는 다른 풀이가 있어 참고하시면 될 것 같습니다. 

<Lv.3> 2차원 동전 뒤집기 (프로그래머스 : C#)

 

제 방법은 모든 행과 열에 대해서 뒤집거나 안뒤집는 경우를 모두 생각해 주었다면 

 

위 블로그에서는 행을 기준으로 뒤집었을때 열을 목표상태로 만들수 있는지를 확인하며 넘어가는 방법이였습니다. 

모두 탐색하는 제 방법보다는 빨라보였습니다. 

 

물론 저도 완전 탐색은 아니지만 위 블로그에서의 코드는 약간 계산 비교...? 

 

참고하시면 될 것 같습니다!