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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

처음에는 이 문제를 DFS나 완전탐색으로 풀어도 괜찮겠다는 생각이 들었다.

 

왜냐하면 가로 세로가 최대 10이였고, 한 줄을 키거나 끌 수 있기 때문에 경우의 수가 약 2^20 이고, 추가로 변환을 했을 때 일치하는지 검사를 할 경우 100개의 동전을 검사하므로 약 1억 정도면 충분하지 않을까? 라는 생각이 들었다.

 

문제는 완전 탐색을 했더니 시간 초과가 걸렸고, 다른 방법을 생각하게 됐다.

 

 

문제에서 핵심은 target의 y, x의 값과 beginning의 y, x의 동일한지 여부다.

즉, target의 y, x의 값과 beginning의 y, x의 값이 다르다면 가로축이나 세로축으로 바꿔야 한다는 뜻이다.

 

이를 이용하면 아래의 순서를 따라 문제를 해결할 수 있다.

 

target과 beginning의 맨 윗줄의 동전을 비교하고 다른 경우 그 동전이 포함된 세로줄을 뒤집는다.

그 다음은  target과 beginning의 맨 왼쪽줄의 동전을 비교하고 다른 경우 그 동전이 포함된 가로줄을 뒤집는다.

 

이후 target과 beginning이 전부 같은지 비교한다.

 

여기서 전부 같지 않으면 -1을 return하면 되고, 만약 같을 경우 뒤집은 횟수를 이용해 어떤 값을 return할지 정한다.

 

어떤 값을 return 할 지는 아래 그림을 참고하자

여기서 1은 target과 beginning이 다른 부분을 의미한다고 하자, 그러면 동전을 뒤집어서 target과 beginning을 같게 만드는 경우는 아래와 같다.

 

1. 1열을 뒤집는 경우

2. 2열과 3열을 뒤집고, 1, 2, 3 행을 뒤집는 경우

그림을 참고하면 두 경우는 전부 같은 모양을 만들고, 두 경우의 뒤집는 횟수를 더하면 y축의 길이+x축의 길이와 같음을 알 수 있다. 

 

그러므로 [뒤집은 횟수,  y축길이+x축 길이-뒤집은 횟수] 중 작은 값을 return하면 된다.

​

[아이디어 정리]

1. target과 beginning의 1열을 기준으로 값이 같은지 다른지 비교하고, 다를 경우 그 값이 포함된 행을 전부 뒤집는다.
2. target과 beginning의 1행을 기준으로 값이 같은지 다른지 비교하고, 다를 경우 그 값이 포함된 열을 전부 뒤집는다.
3. 변환된 target과 beginning을 비교하고 다를 경우 -1을 return한다.
4. 만약 같을 경우 [뒤집은 횟수,  y축길이+x축 길이-뒤집은 횟수] 중 작은 값을 return하면 된다.

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

bool equal(vector<vector<int>> &beginning, vector<vector<int>> &target, int &y, int &x)
{    
    for (int i=0; i<y; i++)
    {
        for (int j=0; j<x; j++)
        {
            if (beginning[i][j]!=target[i][j])
            {            
                return false;
            }
        }
    }
    return true;
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0, y= beginning.size(), x=beginning[0].size();
    for (int i=0; i<x; i++)
    {
        if (beginning[0][i]!=target[0][i])
        {
            for (int j=0; j<y; j++)
            {
                beginning[j][i]=(beginning[j][i]+1)%2;
            }
            answer+=1;
        }
    }
    for (int i=0; i<y; i++)
    {
        if (beginning[i][0]!=target[i][0])
        {
            for (int j=0; j<x; j++)
            {
                beginning[i][j]=(beginning[i][j]+1)%2;
            }
            answer+=1;
        }
    }

    if (equal(beginning,target,y,x))
    {
        return min(answer,y+x-answer);
    }
    return -1;
}

 

---

 

DFS로 문제를 풀 때, 헷갈렸는데 겨우 코드를 작성해 풀었다...

문제는 완전탐색이라 시간이 많이 걸렸는데 덕분에 더 좋은 풀이가 생각났다.

실제로 이런 문제를 풀게 되면 풀이가 시간안에 바로 생각이 날까...? 

 

 

프로그래머스