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

해설

bfs문제이다.

상하좌우로만의 이동이 아니라 ctrl 을 누른 상태에서의 방향키 상태가 추가되었다.

비슷한 문제를 코딩테스트에서 만난적이 있어서.. 미리 풀어봤으면 얼마나 좋았을까 하고 후회중 ㅠ

프로그래머스에 들어가보면 2번째 예시 케이스는 카드의 짝을 맞출때 특정 순서대로 해야만 가능한 상황이 존재한다.

따라서 순열을 만들어주는 next_permutation 함수도 필요하다.

만들어진 순열에 맞춰 각각 bfs를 실행해주면 된다. 시작 지점 -> 첫 번째 카드 -> 첫 번째 카드와 짝 카드 의 위치로 움직이면 되고 순열의 순서대로 실행해준다. 함수 파라미터로 & 을 받으면 구현을 쉽게 할 수 있다.

ctrl 을 눌렀을 때도 현재의 방향으로 모서리를 만날 때 까지 가주면 된다.

---

문제 설명

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.

게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.

유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

게임에서 카드를 선택하는 방법은 다음과 같습니다.

• 카드는 커서를 이용해서 선택할 수 있습니다.
  • 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
• 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
  • [Enter] 키를 입력해서 카드를 뒤집었을 때
    • 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
    • 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.

아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.

---

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int defense[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

int bfs(vector<vector<int>>& board, int card, int& r, int& c)
{
     vector<vector<bool>> visited(board.size(), vector<bool>(board.size(), false));
    queue < pair<pair<int, int>, int>> q;
    q.push({ {r,c},0 });
    visited[r][c] = true;

    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int v = q.front().second;
        q.pop();

        if (board[x][y] == card)
        {
            board[x][y] = 0;
            r = x;
            c = y;
            return v + 1;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + defense[i][0];
            int ny = y + defense[i][1];

            if (nx >= 0 && ny >= 0 && nx < board.size() 
                && ny < board[0].size() && !visited[nx][ny])
            {
                visited[nx][ny] = true;
                q.push({ {nx,ny},v + 1 });
            }

            // ctrl
            int cnx = x;
            int cny = y;
            while (cnx + defense[i][0] >= 0 && cny + defense[i][1] >= 0 &&
                cnx + defense[i][0] < board.size() && cny + defense[i][1] < board[0].size())
            {
                cnx += defense[i][0];
                cny += defense[i][1];
                if (board[cnx][cny])
                    break;
            }
            if (!visited[cnx][cny])
            {
                visited[cnx][cny] = true;
                q.push({ {cnx,cny},v + 1 });
            }
        }

    }
}

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

    for (int i = 0; i < board.size(); i++)
        for (int j = 0; j < board[i].size(); j++)
            if (board[i][j])
                Cards.push_back(board[i][j]);

    sort(Cards.begin(), Cards.end());
    Cards.erase(unique(Cards.begin(), Cards.end()), Cards.end());

    do
    {
        vector<vector<int>> b = board;
        int r2 = r;
        int c2 = c;
        int temp = 0;
        for (int i = 0; i < Cards.size(); i++)
            temp += bfs(b, Cards[i], r2, c2) + bfs(b, Cards[i], r2, c2);
        answer = min(answer, temp);
    } while (next_permutation(Cards.begin(), Cards.end()));


    return answer;
}