[프로그래머스/C++] 격자 뒤집기 미로

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 예외와 조건을 잘 제한해주면 풀 수 있는 문제다.

 

먼저 1,1에서 출발해 n,m까지 도착하는 경우를 생각해보자.

 

당연하게도 각 칸의 점수들은 전부 양수이므로 모든 칸을 밟는게 점수가 높다.

 

여기서 중요한 점은 그런데 가로와 세로 중 한 방향이라도 홀수면 모든 칸을 밟을 수 있지만, 가로와 세로가 전부 짝수면 모든 칸을 밟는 방법이 없다는 것이다.

 

그렇다면 가로와 세로가 전부 짝수인 경우에 어떤 방법이 최선일까?

 

이 경우에 가로와 세로를 더한 값이 홀수인 칸을 하나 빼고 모든 칸을 방문하는 경우가 최선이다.

왜냐하면 가로와 세로를 더 한 값이 2로 나눈칸을 방문하지 않으면 가로와 세로를 더한 값이 홀수인 칸을 무조건 하나 더 방문하지 못하게 되기 때문이다.

(그림을 그려서 예외를 생각해보면 된다...)

 

이제 세로와 가로의 줄 수에 따라 최선의 경우를 알아봤으므로 구현을 통해 모든 칸을 방문하거나, 한 칸을 빼고 모든 칸을 방문하는 방법을 구현하면 된다.

 

방문하는 방법을 알았으니 어떤 경우가 뒤집어서 만들 수 있는 최선의 값인지 계산해보자.

 

이 문제의 경우 가로 방향 길이는 최대 14이지만, 세로 방향 길이는 최대 100이다.

그러므로 세로 줄을 뒤집는 모든 방법을 계산하면 2^14가 된다. (약 16000)

 

이에 대해 가로줄을 뒤집었을 경우 뒤집기 전의 가로줄 합 과 뒤집은 후의 가로줄 합 - 비용을 비교해서 만약 뒤집기 전의 가로줄 합이 더 적다면 뒤집으면 된다.

이러한 방식으로 계산할 경우 16000*100의 경우만 계산하면 되기 때문에 약 100만번의 계산으로 문제를 해결할 수 있다.

(하지만 100번의 경우마다 계속 합을 비교할 경우는 16000*100*14의 계산이 필요하므로 누적합으로 미리 계산해 둔 값을 변경하는 방법으로 하면 좀 더 빨리 해결할 수 있다... 엄청 큰 차이는 없을듯;;)

 

위 방법은 모든 칸을 방문한다고 계산한 방법이므로 만약 가로와 세로가 전부 짝수인 경우는 예외처리를 한번 더 해주어야한다. 

 

이 경우 어떤 칸을 빼고 방문하는게 가장 이득인지 계산을 해야한다.

그러므로 어느 칸을 뒤집지 않을지 정하고 값을 비교하는 방법을 추가해 계산하면 된다.

즉, 위 방법과 비슷하지만, 어느 칸을 방문하지 않을지 비교해야하므로 16000*100*14의 경우를 계산하게 된다.

 

 

​

[아이디어 정리]

1. 세로와 가로줄이 전부 짝수인 경우와 아닌 경우로 구분한다.
2. 세로와 가로줄이 전부 짝수인 경우 모든 칸을 방문하는 방법은 없으며, 가로와 세로의 합이 홀수인 칸을 하나 방문하지 않고 모든 칸을 방문하는 방법이 최선이다.
3. 가로방향으로 줄의 최대값이 14이므로 세로줄을 뒤집는 모든 경우에 대해 계산하는 게 효율적이다. (최대 약 16000)
4. 이후 가로줄을 뒤집을 경우 비용과 변경 후 값을 비교해 어느 경우가 최선인지 구한다.
5. 만약 가로와 세로가 전부 짝수인 경우는 어느 칸을 빼는 게 최선인지 비교하며 계산해주어야 한다.
   

 

 

Code

 

 

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

using namespace std;

int answer;

void dfs(vector<vector<int>> &visible, vector<vector<int>> &hidden, vector<bool> &visited, int dpt, bool tf, int k)
{
    if (dpt<visited.size())
    {
        visited[dpt]=true;
        dfs(visible, hidden, visited, dpt+1, tf, k);
        visited[dpt]=false;
        dfs(visible, hidden, visited, dpt+1, tf, k);
    }
    else
    {
        int cAns=0;
        for (int i=0; i<visited.size(); i++){
            if (visited[i])
            {
                cAns-=k;                
            }
        }
        
        if (tf) //true라면 전부 선택 가능
        {
            for (int m=0; m<visible[0].size(); m++)
            {            
                int nB=0, nF=0;
                for (int n=0; n<visible.size(); n++)
                {
                    if (visited[n]) //true면 뒤집힌 상태
                    {
                        nF+=hidden[n][m];
                        nB+=visible[n][m];
                    }
                    else
                    {
                        nF+=visible[n][m];
                        nB+=hidden[n][m];
                    }
                }
                if (nB-k>nF){
                    cAns+=nB-k;
                }
                else{
                    cAns+=nF;
                }
            }
            answer=max(answer,cAns);
        }
        else
        {
            vector<int> vnB(visible[0].size(),0);
            vector<int> vnF(visible[0].size(),0);
            vector<int> minF(visible[0].size(),10000);
            vector<int> minB(visible[0].size(),10000);
            
            for (int m=0; m<visible[0].size(); m++)
            {            
                for (int n=0; n<visible.size(); n++)
                {
                    if (visited[n]) //true면 뒤집힌 상태
                    {
                        vnF[m]+=hidden[n][m];
                        vnB[m]+=visible[n][m];
                        if ((n+m)%2==1)
                        {
                            minF[m]=min(minF[m], hidden[n][m]);
                            minB[m]=min(minB[m], visible[n][m]);
                        }
                    }
                    else
                    {
                        vnF[m]+=visible[n][m];
                        vnB[m]+=hidden[n][m];
                        if ((n+m)%2==1)
                        {
                            minF[m]=min(minF[m], visible[n][m]);
                            minB[m]=min(minB[m], hidden[n][m]);
                        }
                    }
                }
                if (vnB[m]-k>vnF[m]){
                    cAns+=vnB[m]-k;                    
                }
                else{
                    cAns+=vnF[m];                    
                }
            }
            
            int tmp;
            for (int i=0; i<visible[0].size(); i++)
            {
                tmp=cAns;
                //i번째 줄에서 뺄 수를 선택한다는 뜻
                if (vnB[i]-k>vnF[i]){
                    tmp-=vnB[i]-k;                    
                }
                else{
                    tmp-=vnF[i];                    
                }
                
                if (vnB[i]-k-minB[i]>vnF[i]-minF[i]){
                    tmp+=vnB[i]-k-minB[i];                    
                }
                else{
                    tmp+=vnF[i]-minF[i];                    
                }
                answer=max(answer,tmp);
            }
        }
    }
}

int solution(vector<vector<int>> visible, vector<vector<int>> hidden, int k) {
    answer = 0;
    int y, x;
    x=visible[0].size(), y=visible.size();
    bool tf;
    if (x%2==0&&y%2==0){
        tf=false;
    }
    else{
        tf=true;
    }
    vector<bool> visited(visible.size());
    dfs(visible, hidden, visited, 0, tf, k);
    return answer;
}

---

 

최근에 노느라 바뻐서 문제를 거의 풀지 않았다...

이 문제는 다행히 이전에 풀었던 문제와 비슷해서 풀이는 바로 생각났는데, 예외를 생각하지 못해서 오래 걸린 문제였다.

가로와 세로가 전부 짝수일 경우 가로와 세로의 합이 짝수인 칸을 하나만 방문하지 않는 방법이 없다는 예외를 직접 그려보고 겨우 풀 수 있었다... ㅠㅠㅠ

 

 

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