[1일 1알고] 카드 짝 맞추기

해당 문제는 빡센 구현 문제입니다. 간단해보이지만 여러가지 기술이 합쳐진 컴비네이션 문제입니다.

 

기본적으로 뒤집어야할 카드의 위치는 모두 공개되어있습니다. 

최소 이동값을 구해야하는데 이를 위해 카드를 어떤 순서로 뒤집어야할지 정해야합니다.

 

최대 카드는 6개까지이고, 카드의 한쪽을 고르면 반드시 다음 선택은 같은 번호의 짝 카드이기 때문에 최대 경우의 수는 12 * 10 * 8 ... * 2일 것입니다. 따라서 모든 경우를 따져도 시간초과가 발생할 문제는 아닙니다.

각 경우를 탐색하기 위해서는 조합을 만드는 것 처럼 dfs를 사용해야할 것입니다.

 

또한 카드를 고를 때 같은 번호라도 어떤 것을 먼저고르는지에 따라 경우가 달라지기 때문에 이는 별도로 백트래킹으로 관리해야할 것입니다.

---

카드에서 카드 간 이동하는 거리를 구하기 위해서는 최단거리를 구해야하기 때문에 bfs를 사용해야합니다.

4x4이기 때문에 다행히도 이것도 비용이 그렇게 크지는 않을 것입니다.

 

다만 이동의 경우가 상하좌우 이동 + ctrl 상하좌우 이동이기 때문에 매칸마다 8개의 이동 경우를 확인해야합니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <climits>
#include <map>
#include <queue>
#include<set>
using namespace std;

// 4x4의 카드가 뒷면상태
// 8개의 캐릭터가 2장씩 무작위로 배치되어있음
// 짝맞추기 형태의 게임

// 선택법
// 커서를 통해 선택 ->  엔터로 뒤집기

struct Pos
{
    int r, c;
};

int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

int dist(Pos start, Pos target, vector<vector<int>>& board)
{
    int result = 17;
    queue<Pos> q;
    q.push(start);

    int visited[4][4];

    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
            visited[i][j] = -1;
    }
    visited[start.r][start.c] = 0;
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        if (cur.r == target.r && cur.c == target.c)
        {
            return visited[cur.r][cur.c];
        }

        for (int i = 0; i < 4; ++i)
        {
            int nr = cur.r + dr[i];
            int nc = cur.c + dc[i];
            if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4 && visited[nr][nc] == -1)
            {
                visited[nr][nc] = visited[cur.r][cur.c] + 1;
                q.push({nr, nc});
            }
        }
        for (int i = 0; i < 4; ++i)
        {
            int nr = cur.r;
            int nc = cur.c;
            while (true)
            {
                int tr = nr + dr[i];
                int tc = nc + dc[i];

                if (tr < 0 || tr >= 4 || tc < 0 || tc >= 4)
                {
                    if (visited[nr][nc] == -1)
                    {
                        visited[nr][nc] = visited[cur.r][cur.c] + 1;
                        q.push({ nr, nc });
                    }
                    break;
                }

                nr = tr;
                nc = tc;
                if (board[nr][nc] != 0)
                {
                    if (visited[nr][nc] == -1)
                    {
                        visited[nr][nc] = visited[cur.r][cur.c] + 1;
                        q.push({ nr, nc });
                    }
                    break;
                }
            }
        }
    }
}
int answer = 10000000;

void dfs(Pos cur, vector<vector<int>>& board, 
    set<int>& cards, int totalcost, int remaincnt)
{
    if (remaincnt == 0)
    {
        answer = min(answer, totalcost);
        return;
    }

    vector<int> cardList(cards.begin(), cards.end());

    for (int card : cardList)
    {
        Pos target[2];
        target[0] = { 0, 0 };
        target[1] = { 0, 0 };
        int idx = 0;
        for (int i = 0; i < 4; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                if (board[i][j] == card)
                {
                    target[idx].r = i;
                    target[idx].c = j;
                    ++idx;
                }
            }
        }

        int cost1 = dist(cur, target[0], board) + dist(target[0], target[1], board);
        if (cost1 < 0)
        {
            cout << "ERROR!";
        }
        board[target[0].r][target[0].c] = 0;
        board[target[1].r][target[1].c] = 0;
        cards.erase(card);
        dfs(target[1], board, cards, totalcost + cost1, remaincnt - 1);
        cards.insert(card);
        board[target[0].r][target[0].c] = card;
        board[target[1].r][target[1].c] = card;

        int cost2 = dist(cur, target[1], board) + dist(target[1], target[0], board);
        if (cost1 < 0)
        {
            cout << "ERROR!";
        }
        board[target[0].r][target[0].c] = 0;
        board[target[1].r][target[1].c] = 0;
        cards.erase(card);
        dfs(target[0], board, cards, totalcost + cost2, remaincnt - 1);
        cards.insert(card);
        board[target[0].r][target[0].c] = card;
        board[target[1].r][target[1].c] = card;
    }
}

int solution(vector<vector<int>> board, int r, int c) {
    
    set<int> cards;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (board[i][j] != 0)
                cards.insert(board[i][j]);
        }
    }
    int cardcnt = cards.size();
    Pos cur;
    cur.r = r;
    cur.c = c;

    dfs(cur, board, cards, 0, cardcnt);
    return answer + cardcnt * 2;
}

 

코드에 미흡한 점이 많지만 그래도 원하는 바는 다 구현을 했습니다.