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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72415

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

문제 유형

BFS, DFS, Brute Force, 구현

 

2021 카카오 블라인드 코딩 테스트의 6번 문제이다.

게임판의 크기가 4x4로 매우 작고, 카드의 종류도 6가지이므로

각 카드를 찾는 모든 순서에 대해(완전 탐색) 이동 횟수를 구한 후 이들 중 최솟값을 구하면 된다.

이 풀이에서는 이동 횟수를 구하는 데 BFS를, 카드를 맞추는 순서에 대한 순열을 DFS로 구현했다.

주의할 것은, 예시로 3번 카드를 맞출 순서일 때, 3번 카드는 총 두 장이 있으므로 각 두 카드에 대해 이동 횟수를 모두 구해줘야 올바른 답을 구할 수 있다.

93번째 줄부터 res_12, res_21 각 경우에 대해 모두 DFS 재귀를 해줌으로써 비는 케이스 없이 완전 탐색이 가능하다.

 

[코드]

#include <string>
#include <vector>
#include <queue>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> pp;
 
p dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
 
bool card_use[7];
int fullstate, ans = 99999999;
p card_pos[7][2];
 
p get_edge(p pos, int dir){
    if(dir == 0) return {pos.first, 3};
    if(dir == 1) return {3, pos.second};
    if(dir == 2) return {pos.first, 0};
    return {0, pos.second};
}
 
int bfs(vector<vector<int>> board, p start, p target){
    bool visit[4][4];
    memset(visit, false, sizeof(visit));
    queue<pair<int, p>> que;
    que.push({0, start});
    visit[start.first][start.second] = true;
    
    while(!que.empty()){
        pair<int, p> cur = que.front();
        que.pop();
        
        int row = cur.second.first;
        int col = cur.second.second;
        int cnt = cur.first;
        
        if(row == target.first && col == target.second) return cnt;
        
        for(int i = 0; i < 4; i++){
            int newR = row + dir[i].first;
            int newC = col + dir[i].second;
            bool fail = false;
            
            if(newR < 0 || newR > 3 || newC < 0 || newC > 3) continue;
            
            if(!visit[newR][newC]){
                //한 칸 이동
                visit[newR][newC] = true;
                que.push({cnt + 1, {newR, newC}});
            }
            
            if(board[newR][newC]) continue;
            
            while(1){
                newR += dir[i].first;
                newC += dir[i].second;
                if(newR < 0 || newR > 3 || newC < 0 || newC > 3) {fail = true; break;}
                
                if(board[newR][newC] && !visit[newR][newC]){
                    visit[newR][newC] = true;
                    que.push({cnt + 1, {newR, newC}});
                    break;
                }
            }    
            if(fail){
                p edg = get_edge({row, col}, i);
                if(!visit[edg.first][edg.second]){
                    visit[edg.first][edg.second] = true;
                    que.push({cnt + 1, edg});
                }
            }
        }
    }
}
 
void dfs(vector<vector<int>> board, int pos, int state, int cnt){
    
    //모든 카드를 찾았다면
    if(state == fullstate){
        ans = min(ans, cnt);
        return;
    }
    
    //아직 찾지 않은 카드에 대해 탐색
    for(int i = 0; i < 6; i++){
        if(!card_use[i + 1]) continue;      //제시되지 않은 카드
        if(state & 1 << i) continue;        //이미 찾은 카드
        
        vector<vector<int>> board_temp = board;
        
        p cur_pos = {pos / 4, pos % 4};
        int res_12 = bfs(board, cur_pos, card_pos[i + 1][0]) + 
            bfs(board, card_pos[i + 1][0], card_pos[i + 1][1]);
        int res_21 = bfs(board, cur_pos, card_pos[i + 1][1]) + 
            bfs(board, card_pos[i + 1][1], card_pos[i + 1][0]);
        
        board_temp[card_pos[i + 1][0].first][card_pos[i + 1][0].second] = 0;
        board_temp[card_pos[i + 1][1].first][card_pos[i + 1][1].second] = 0;
        
        int pos_12 = card_pos[i + 1][1].first * 4 + card_pos[i + 1][1].second;
        int pos_21 = card_pos[i + 1][0].first * 4 + card_pos[i + 1][0].second;
        
        dfs(board_temp, pos_12, state | (1 << i), cnt + res_12 + 2);
        dfs(board_temp, pos_21, state | (1 << i), cnt + res_21 + 2);
    }
}
 
void setup(vector<vector<int>> board) {
    int fst = 0;
    for(int i = 1; i <= 6; i++) {card_pos[i][0] = {-1, -1}; card_pos[i][1] = {-1, -1};}
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            int card = board[i][j];
            if(card == 0) continue;
            
            if(!card_use[card]){
                card_pos[card][0] = {i, j};
                card_use[card] = true;
            }
            else{
                card_pos[card][1] = {i, j};
            }
            fst |= (1 << (card - 1));
        }
    fullstate = fst;
}
 
int solution(vector<vector<int>> board, int r, int c) {
    int answer = 9999;
 
    setup(board);
    dfs(board, r * 4 + c, 0, 0);
    answer = ans;
    
    return answer;
}