[프로그래머스/C++] 카드 짝 맞추기

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 카드 짝을 맞추는 최소 횟수를 구하면 되는 문제다.

 

그렇기 때문에 이동횟수가 최소가 되는 경우를 구하기 위해서는 BFS로 a에서 목적지까지 가는데 걸리는 입력 횟수가 최소가 되도록 계산하면 된다.

 

그리고 카드를 뒤집는 순서도 게임에 중요하다 예를 들면 a카드를 뒤집고 b카드를 뒤집는 경우와 b카드를 뒤집고 a카드를 뒤집는 경우가 최소 횟수가 다를 수 있다는 의미다.

 

그래서 카드의 순서에 대한 모든 경우를 구해 카드를 뒤집는 순서를 구하고, 그 순서에 따라 BFS로 최소 횟수를 구했다.

 

이후 모든 경우에 대해 입력이 최소가 되는 횟수를 return하면 된다.

 

 

[아이디어 정리]

1. 카드를 뒤집는 순서에 대한 경우를 모두 구한다.
2. 그 순서에 따라 카드를 뒤집는데 이때 최소 횟수를 BFS로 구한다.
3. 구한 경우중에 최소가 되는 입력 횟수를 return하면 된다.

 

Code

 

 

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

vector<vector<int>> realBoard;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
// 횟수와 자리를 반환하는 함수
vector<int> calc(pair<int,int> st, int cardN)
{
    queue<pair<int,int>> Q;
    queue<int> Cnt;
    vector<vector<bool>> visited(4,vector<bool>(4,false));
    visited[st.first][st.second]=true;
    Q.push(st);
    Cnt.push(0);
    pair<int,int>nowP;
    int nowC,ny,nx;
    
    while(!Q.empty())
    {
        nowP=Q.front();
        Q.pop();
        nowC=Cnt.front();
        Cnt.pop();
        if (realBoard[nowP.first][nowP.second]==cardN)
        {
            vector<int> a(3,0);
            a[0]=nowP.first;
            a[1]=nowP.second;
            a[2]=nowC+1; //enter키
            realBoard[a[0]][a[1]]=0; // 눌렀음
            return a;
        }
        for (int i=0;i<4; i++)
        {
            ny=nowP.first+dy[i];
            nx=nowP.second+dx[i];
            if (ny>=0&&ny<4 && nx>=0&&ny<4 && !visited[ny][nx])
            {
                Q.push(make_pair(ny,nx));
                Cnt.push(nowC+1);
                visited[ny][nx]=true;
            }
        }
        ny=nowP.first;
        nx=nowP.second;
        for (int i=nowP.second+1; i<4; i++)
        {
            if (realBoard[ny][i]!=0)
            {
                if(!visited[ny][i])
                {
                    Q.push(make_pair(ny,i));
                    Cnt.push(nowC+1);
                    visited[ny][i]=true;
                }
                break;                        
            }
            if (i == 3)
            {
                if(!visited[ny][i])
                {
                    Q.push(make_pair(ny,i));
                    Cnt.push(nowC+1);
                    visited[ny][i]=true;
                }
            }
        }
        for (int i=nowP.second-1; i>=0; i--)
            {
                if (realBoard[ny][i]!=0)
                {
                    if(!visited[ny][i])
                    {
                        Q.push(make_pair(ny,i));
                        Cnt.push(nowC+1);
                        visited[ny][i]=true;
                    }
                    break;                        
                }
                if (i == 0)
                {
                    if(!visited[ny][i])
                    {
                        Q.push(make_pair(ny,i));
                        Cnt.push(nowC+1);
                        visited[ny][i]=true;
                    }
                }
            }
            for (int i=nowP.first+1; i<4; i++)
            {
                if (realBoard[i][nx]!=0)
                {
                    if(!visited[i][nx])
                    {
                        Q.push(make_pair(i,nx));
                        Cnt.push(nowC+1);
                        visited[i][nx]=true;
                    }
                    break;                        
                }
                if (i == 3)
                {
                    if(!visited[i][nx])
                    {
                        Q.push(make_pair(i,nx));
                        Cnt.push(nowC+1);
                        visited[i][nx]=true;
                    }
                }
            }
            for (int i=nowP.first-1; i>=0; i--)
            {
                if (realBoard[i][nx]!=0)
                {
                    if(!visited[i][nx])
                    {
                        Q.push(make_pair(i,nx));
                        Cnt.push(nowC+1);
                        visited[i][nx]=true;
                    }
                    break;                        
                }
                if (i == 0)
                {
                    if(!visited[i][nx])
                    {
                        Q.push(make_pair(i,nx));
                        Cnt.push(nowC+1);
                        visited[i][nx]=true;
                    }
                }
            }
    }
    return vector<int>(3,0);
}
vector<vector<int>> returnComb;
vector<bool> vvc;
void combi(vector<int> comb, vector<int>pushV)
{
    if (pushV.size()==comb.size())
    {
        returnComb.push_back(pushV);
    }        
    for (int i=0; i<comb.size(); i++)
    {
        if (!vvc[i])
        {
            vector<int> newV=pushV;
            newV.push_back(comb[i]);
            vvc[i]=true;
            combi(comb,newV);
            vvc[i]=false;
        }
    }
}

int minCnt(vector<vector<int>> copyBoard, int r, int c)
{
    bool cards[9];
    fill_n(cards,9,false);
    for (int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            if (copyBoard[i][j]!=0)
            {
                cards[copyBoard[i][j]]=true;
            }
        }
    }
    vector<int> ccc;
    for (int i=0; i<9; i++)
    {
        if (cards[i])
        {
            ccc.push_back(i);
        }
    }
    
    realBoard=copyBoard;
    vvc =vector<bool>(ccc.size(),false);
    vector<int> ctcc;
    combi(ccc, ctcc);
    int minCnt=16*16;
    
    
    for (int i=0; i<returnComb.size(); i++)
    {
        int ty, tx,nCnt;
        vector<int> ttv;
        realBoard=copyBoard;
        nCnt=0;
        ty=r;
        tx=c;
        for(int j=0; j<returnComb[0].size(); j++)
        {
            for (int k=0; k<2; k++)
            {
                ttv = calc(make_pair(ty,tx), returnComb[i][j]);
                ty=ttv[0];
                tx=ttv[1];
                nCnt+=ttv[2];
            }
        }
        if (nCnt<minCnt)
        {
            minCnt=nCnt;
        }
    }
    return minCnt;
}

int solution(vector<vector<int>> board, int r, int c) {
    realBoard=board;
    pair<int,int> ctt;
    int answer = 0;
    answer=minCnt(board,r,c);
    return answer;
}

 

---

 

문제 자체는 어렵지 않았는데, 재귀를 이용하는 대신 전역변수를 선언하고, 함수를 구현하다 보니 코드가 많이 길어졌다.

게다가 ctrl키를 누르고 한번에 이동하는 코드를 작성할 때, 처음에 y와 x를 잘못 적어서 오류도 생겼다

일단 풀긴 했는데, 생각보다 구현이 힘들었고, 다음부터 쓸모없는 코드들을 줄여 코드 길이를 좀 줄이고 가독성을 높여야겠다;;;

 

프로그래머스