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

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

 

[난이도] level3
[유형] 브루트포스

[풀이]
브루트포스+BFS를 이용한 거리찾기가 결합된 복잡한 구현 문제입니다.
보드가 4x4이고, 나올수 있는 카드의 쌍이 최대 6개라는점을 보고 브루트포스라는 것을 의심해야 합니다.
4x4 맵의 경우 어지간한 문제는 무식하게 풀어도 시간내에 해결이 가능합니다.

이미 카드의 앞면을 알고 있기 때문에 조작 횟수를 최소로 하려면 쓸데없는 칸에 방문하지 않고
카드쌍을 바로바로 제거할 수 있도록 방문해야 합니다.
예를 들어 [1-1/1-2],[2-1/2-2],[3-1/3-2] 총 3쌍의 카드가 있을 때
1-1 -> 1-2 -> 2-2 -> 2-1 -> 3-1 -> 3-2 이런식으로 이동해야 효율적이며
1-1 -> 2-1 -> 1-2 .. 이런식으로 1번카드 갔다가 2번 카드갔다가 하면 불필요한 조작이 늘어납니다.

하지만 어떤 카드부터 지워야 할지는 알수 없기 때문에 모든 경우를 다해봐야 합니다.
next_permutation으로 모든 순서를 구할 수 있습니다.
여기서는 seq vector에 모든 카드 종류를 넣고 순열을 구하였습니다.

하지만 여기서 또 정해야 할것이 1->2->3 순서로 카드를 없애는 경우에서도
1-1 -> 1-2 순서로 방문해서 1을 없애는 경우, 1-2 -> 1-1 순서로 방문해서 1을 없애는 경우가
다른 경우입니다. 2와 3을 방문할때도 같은 종류의 두가지 카드중 어떤 것을 방문할지를 정해야 합니다.

위 과정은 sol(int n) 재귀함수를 통해 백트래킹으로 진행하였습니다.
입력을 받을 때, vector<pair<int,int>> table[7]를 이용해 table[카드 종류]에 같은 종류의 두개의 카드 좌표를 저장해두었습니다.

이를 이용해 vector<pair<int,int>> mseq 에
1->2->3 순서로 카드를 없애는 케이스에서는

(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-1의 좌표),(3-2의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-2의 좌표),(3-1의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-2의 좌표),(2-1의 좌표),(3-1의 좌표),(3-2의 좌표)
...
...
와 같이 모든 케이스가

n==total(카드 종류의 개수) 이 될때 저장되게 됩니다.

이제 시작점 (r,c)를 시작으로 mseq에 저장된 좌표를 순서대로 방문하기만 하면 됩니다.
이제 순서가 정해졌기 때문에 카드의 종류 등은 생각할 필요가 없습니다.
위의 모든 케이스에서 조작 횟수를 구한 후 그것들중에 최솟값을 구하면 됩니다.

bfs(int fy,int fx,int ty,int tx) 함수를 통해 (fy,fx)에서 (ty,tx)로 갈때
드는 최소 조작 횟수를 구해주었습니다. end 함수는 ctrl+방향키 조작했을 때 도착하는
좌표를 구해주는 함수입니다.

mseq의 좌표를 순서대로 방문하면서 카드가 제거되는 순간 board에서 그 좌표의 값은 0으로
만들어 주어야 합니다. 그래서 매 시행마다 board를 복사해서 사용하였습니다.
제거되는 순간은 mseq의 index가 홀수인 순간입니다.
이유는 0,1,2,3,4,5 일때
1을 방문한 순간 0,1(1번카드)
3을 방문한 순간 2,3(2번카드)
5를 방문한 순간 4,5(3번카드)
가 각각 지워지기 때문입니다. 이 때 지워주지 않으면 ctrl+방향 조작시 지워져야 했던 카드에 막혀
올바르지 않은 곳으로 위치할 수 있습니다.

위 과정으로 구한 최솟값에 Enter 연산인 (카드의 종류*2) 를 더해준 것이 최종 정답입니다.

시험시간에 풀었다면 시간내에 풀지 못햇을 것 같은 복잡한 문제입니다.
최대한 과정을 쪼개서 간단한 문제로 만드는 것이 중요한 것 같습니다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
using namespace std;
int total,ans=987654321;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int R,C;
bool visit[4][4];
vector<pair<int,int>> table[7];
vector<int> seq;
vector<pair<int,int>> mseq;
vector<vector<int>> org_board,board;
bool inRagne(int y,int x){
    return y>=0&&x>=0&&y<4&&x<4;
}
pair<int,int> end(int y,int x,int k){
    while(1){
        y+=dy[k]; x+=dx[k];
        if(!inRagne(y,x)){
            y-=dy[k], x-=dx[k];
            break;
        }
        if(board[y][x]>0) break;
    }
    return {y,x};
}
int bfs(int fy,int fx,int ty,int tx){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    visit[fy][fx]=1;
    q.push({fy,fx});
    int ret=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto [y,x] = q.front(); q.pop();
            if(y==ty&&x==tx) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i],nx=x+dx[i];
                if(!inRagne(ny,nx)) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx]=1;
                }
                auto [ky,kx] = end(y,x,i);
                if(!visit[ky][kx]){
                    q.push({ky,kx});
                    visit[ky][kx]=1;
                }
            }
        }
        ret++;
    }
    return -1;
}
void sol(int n){
    if(n==total){
        board = org_board;
        int cy=R,cx=C,res=0;
        for(int i=0;i<mseq.size();i++){
            auto [ny,nx] = mseq[i];
            res+=bfs(cy,cx,ny,nx);
            if(i&1) board[ny][nx]=board[cy][cx]=0;
            cy=ny,cx=nx;
        }
        ans=min(ans,res);
        return;
    }
    int cur = seq[n];
    mseq.push_back(table[cur][0]); mseq.push_back(table[cur][1]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();

    mseq.push_back(table[cur][1]); mseq.push_back(table[cur][0]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();
}
int solution(vector<vector<int>> board, int r, int c) {
    R=r, C=c;
    org_board = board;
    set<int> st;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++) {
            if(board[i][j]>0) {
                st.insert(board[i][j]);
                table[board[i][j]].push_back({i,j});
            }
        }
    total = st.size();
    for(auto v : st) seq.push_back(v);
    do{
        sol(0);
    }while(next_permutation(seq.begin(),seq.end()));
    return ans+st.size()*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/카드_짝_맞추기.cpp