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

프로그래머스 카드 짝 맞추기 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72415

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

문제 풀이

• 이 문제는 모든 카드 쌍을 어떤 순서로 제거할 것인지, 한 카드 쌍에서 두 개의 카드를 어떤 순서로 선택할 것인지를 완전 탐색하여 해결하였습니다. 
• 모든 카드를 어떤 순서로 제거할 것인지 완전 탐색하기 위해 next_permutation을 사용했습니다. 
  • [1, 2, 3]의 카드 쌍이 있을때 해당 vector에 next_permutation을 사용하면 아래에 있는 모든 경우의 수를 만들어줍니다. 
  • 1, 2, 3 / 1, 3, 2 / 2, 1, 3 / 2, 3, 1 / 3, 1, 2 / 3, 2, 1
• 다음으로 1, 2, 3의 순서로 카드를 제거하려고 할 때, 먼저 1번 카드 두 장[A, B]을 각각 다른 순서로 제거하는 것을 고려해야 합니다. 
  • 모든 경우의 수를 고려하기 위해, (현재 위치 -> A + A -> B), (현재 위치 -> B + B -> A) 를 구한 후 각각 사용합니다. (코드를 보시면 이해가 쉬울 것 같습니다!)
• 현재 위치 - 카드, 카드 - 카드의 거리를 구하기 위해 다익스트라(Dijkstra) 알고리즘을 사용했습니다. 

 코드

#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

#define SIZE 4
#define INF 101

vector<int> cards;
vector<pair<int,int>> cardLoc[7];

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int answer = 1e9;

bool safe(int y, int x) {
    return y>=0 && x>=0 && y<SIZE && x<SIZE;    
}

int get_dist(vector<vector<int>> &board, int sy, int sx, int ty, int tx) {
    vector<vector<int>> dist(SIZE, vector<int>(SIZE, INF));
    priority_queue<tuple<int,int,int>> pq;
    
    pq.push({0, sy, sx});
    dist[sy][sx] = 0;
    
    // 다익스트라 알고리즘으로 두 지점 거리 구하기
    while(!pq.empty()) {
        auto [cnt, y, x] = pq.top(); pq.pop();
        cnt = -cnt;
        
        if(y == ty && x == tx) return cnt;
        
        for(int d=0; d<4; ++d) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            
            if(!safe(ny, nx)) continue;
            
            if(cnt + 1 < dist[ny][nx]) {
                dist[ny][nx] = cnt + 1;
                pq.push({-(cnt+1), ny, nx});
            }
            
            // Ctrl + 방향키
            while(safe(ny, nx) && board[ny][nx] == 0) {
                ny += dy[d];
                nx += dx[d];
            }
            if(!safe(ny, nx)) {
                ny -= dy[d];
                nx -= dx[d];
            }
            
            if(cnt + 1 < dist[ny][nx]) {
                dist[ny][nx] = cnt + 1;
                pq.push({-(cnt+1), ny, nx});
            }
        }
    }
    
    return -1;
}

void func(vector<vector<int>> &board, int idx, int ans, int y, int x) {
    if(idx == cards.size()) {
        answer = min(answer, ans);
        return;
    }
    
    int card = cards[idx];
    pair<int,int> loc1 = cardLoc[card][0]; 
    pair<int,int> loc2 = cardLoc[card][1]; 
    
    // 카드 다른 순서로 뒤집기
    int dist1 = get_dist(board, y, x, loc1.first, loc1.second) + 
        get_dist(board, loc1.first, loc1.second, loc2.first, loc2.second) + 2;
    
    int dist2 = get_dist(board, y, x, loc2.first, loc2.second) +
        get_dist(board, loc2.first, loc2.second, loc1.first, loc1.second) + 2;
        
    board[loc1.first][loc1.second] = 0;
    board[loc2.first][loc2.second] = 0;
    
    func(board, idx+1, ans+dist1, loc2.first, loc2.second);
    func(board, idx+1, ans+dist2, loc1.first, loc1.second);
    
    board[loc1.first][loc1.second] = card;
    board[loc2.first][loc2.second] = card;
}

int solution(vector<vector<int>> board, int r, int c) {
    for(int i=0; i<SIZE; ++i) {
        for(int j=0; j<SIZE; ++j) {
            if(board[i][j]) {
                cards.push_back(board[i][j]); // 모든 카드 담기
                cardLoc[board[i][j]].push_back({i, j});
            }
        }
    }
    
    sort(cards.begin(), cards.end());
    cards.erase(unique(cards.begin(), cards.end()), cards.end());
    
    do {
        func(board, 0, 0, r, c);
    } while(next_permutation(cards.begin(), cards.end()));
    
    return answer;
}

실행 결과