프로그래머스 - 카드 짝 맞추기 (Cpp)

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

문제 풀이

좌표를 이동할 때 고려해야 하는 상황이 2가지가 있다 첫 번째 상, 하, 좌, 우 한칸씩 이동하는 경우와 한번에 카드가 있는 곳이나 벽쪽으로 바로 이동하는 경우다.
카드를 찾는 경우의 수를 만드는데 있어 고려해야 하는 사항이 2가지가 있다. 첫번째는 서로 다른 카드를 찾아가는 경우의 수와 같은 숫자를 찾는 순서를 정하는 경우의 수다.
예를 들어 1 -> 2 -> 3 의 순서로 카드를 찾아간다고 하면 (1 -> 1 짝 찾는 순서) -> (2 -> 2 짝 찾는 순서) -> (3 -> 3 짝 찾는 순서) 를 고려해야 한다는 의미다.

경우의 수가 만들어지면 각 순서에 맞게 BFS를 이용해 최단거리를 구해주면 된다. 다만, 카드는 짝을 만다면 사라지므로 최단 거리를 찾을 때 board 에서 카드가 사라졌는지에 대한 여부도 고려하면서 이동해줘야 한다.

고려 사항

• enter를 누르는 것도 count 1을 갖는다.
• 카드 뒤집는 모든 경우의 수를 계산해야 한다.
  • 1, 2, 3 서로 다른 카드를 찾아가는 경우의 수를 찾는다. 각각의 순서를 고려 하므로 순열의 경우의 수를 갖는다.
  • 1 -> 1, 2 -> 2, 3 -> 3 각각 짝을 만드는 방향이 단방향으로 정해진 것이 아니기 때문에 반대 방향에 대해서도 고려애 줘야 한다.
  • 즉, 최대 경우의 수는 6! * 2 ^ 6 이된다.
• 이동할 때 카드가 사라졌는지 확인해야 한다.

board 에서 각 카드의 위치 찾기

int findCards(vector<vector<int>>& board) {
    int count = 0;

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int value = board[i][j];

            if (value > 0) {
                cards[value].push_back({i, j});
                count++;
            }
        }
    }
    return (count / 2);
}

카드를 뒤집는 모든 경우의 수 찾기

void findAllOrderCase(int depth) {
    if (depth == cardCount * 2) {
        allOrderCase.push_back(oneOrderCase);
        return;
    }

    for (int i = 1; i < 7; i++) {
        if (cards[i].size() > 0 && checkOrder[i] == false) {
            pair<int, int> point1 = cards[i][0];
            pair<int, int> point2 = cards[i][1];

            checkOrder[i] = true;

            oneOrderCase[depth] = point1;
            oneOrderCase[depth + 1] = point2;
            findAllOrderCase(depth + 2);

            oneOrderCase[depth] = point2;
            oneOrderCase[depth + 1] = point1;
            findAllOrderCase(depth + 2);

            checkOrder[i] = false;
        }
    }
}

한 점에서 다른 점까지의 최단거리 구하기

int bfs(vector<vector<int>>& board, pair<int, int> startPoint, pair<int, int> endPoint) {
    queue<pair<int, int>> q;
    q.push({startPoint.first, startPoint.second});

    int count = 0;
    while (!q.empty()) {
        int q_size = q.size();
        while (q_size--) {
            int cntY = q.front().first;
            int cntX = q.front().second;
            q.pop();

            if (cntY == endPoint.first && cntX == endPoint.second) {
                if (board[startPoint.first][startPoint.second] == board[endPoint.first][endPoint.second]) {
                    isDisappear[startPoint.first][startPoint.second] = true;
                    isDisappear[endPoint.first][endPoint.second] = true;
                }

                return count + 1;
            }

            for (int i = 0; i < 4; i++) {
                int ny = cntY + dy[i];
                int nx = cntX + dx[i];

                if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
                    continue;
                }
                q.push({ny, nx});

                while (0 <= (ny + dy[i]) && (ny + dy[i]) < 4 && 0 <= (nx + dx[i]) && (nx + dx[i]) < 4 && (board[ny][nx] == 0 || isDisappear[ny][nx] == true)) {
                    ny += dy[i];
                    nx += dx[i];
                }
                q.push({ny, nx});
            }
        }
        count++;
    }
    return count;
}

전체 소스 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;

vector<pair<int, int>> cards[7];
int cardCount = 0;
bool checkCard[7];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

bool checkOrder[7];
vector<pair<int, int>> oneOrderCase;
vector<vector<pair<int, int>>> allOrderCase;
vector<vector<bool>> isDisappear;

int findCards(vector<vector<int>>& board) {
    int count = 0;

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int value = board[i][j];

            if (value > 0) {
                cards[value].push_back({i, j});
                count++;
            }
        }
    }
    return (count / 2);
}

void findAllOrderCase(int depth) {
    if (depth == cardCount * 2) {
        allOrderCase.push_back(oneOrderCase);
        return;
    }

    for (int i = 1; i < 7; i++) {
        if (cards[i].size() > 0 && checkOrder[i] == false) {
            pair<int, int> point1 = cards[i][0];
            pair<int, int> point2 = cards[i][1];

            checkOrder[i] = true;

            oneOrderCase[depth] = point1;
            oneOrderCase[depth + 1] = point2;
            findAllOrderCase(depth + 2);

            oneOrderCase[depth] = point2;
            oneOrderCase[depth + 1] = point1;
            findAllOrderCase(depth + 2);

            checkOrder[i] = false;
        }
    }
}

int bfs(vector<vector<int>>& board, pair<int, int> startPoint, pair<int, int> endPoint) {
    queue<pair<int, int>> q;
    q.push({startPoint.first, startPoint.second});

    int count = 0;
    while (!q.empty()) {
        int q_size = q.size();
        while (q_size--) {
            int cntY = q.front().first;
            int cntX = q.front().second;
            q.pop();

            if (cntY == endPoint.first && cntX == endPoint.second) {
                if (board[startPoint.first][startPoint.second] == board[endPoint.first][endPoint.second]) {
                    isDisappear[startPoint.first][startPoint.second] = true;
                    isDisappear[endPoint.first][endPoint.second] = true;
                }

                return count + 1;
            }

            for (int i = 0; i < 4; i++) {
                int ny = cntY + dy[i];
                int nx = cntX + dx[i];

                if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
                    continue;
                }
                q.push({ny, nx});

                while (0 <= (ny + dy[i]) && (ny + dy[i]) < 4 && 0 <= (nx + dx[i]) && (nx + dx[i]) < 4 && (board[ny][nx] == 0 || isDisappear[ny][nx] == true)) {
                    ny += dy[i];
                    nx += dx[i];
                }
                q.push({ny, nx});
            }
        }
        count++;
    }
    return count;
}

int solution(vector<vector<int>> board, int r, int c) {
    int answer = 0;

    cardCount = findCards(board);
    oneOrderCase = vector<pair<int, int>>(cardCount * 2);
    findAllOrderCase(0);

    int minDist = INF;

    for (vector<pair<int, int>> points : allOrderCase) {
        isDisappear = vector<vector<bool>>(4, vector<bool>(4, false));
        pair<int, int> startPoint = {r, c};
        int cntDist = 0;

        for (int i = 0; i < points.size(); i++) {
            pair<int, int> endPoint = points[i];

            int value = bfs(board, startPoint, endPoint);
            cntDist += value;
            startPoint = endPoint;
        }
        minDist = min(minDist, cntDist);
    }
    answer = minDist;

    return answer;
}