[프로그래머스] [Level3][c++][bfs][permutation] 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기 - 컴도리돌이

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

 

1. 카드의 수가 6장으로 제한되어 있다. 그렇기에 카드 숫자에 따른 순열 조합으로 가장 최단 거리를 조사했다.
2. 먼저 board에 있는 카드의 숫자를 card 벡터에 저장하여, 중복된 숫자는 제거하고 next_permutation으로 bfs 탐색을 한다.
3. bfs로 카드를 탐색하기 전에 각 순열마다 최소 거리를 구해야하기 때문에 순열이 돌때마다 board와 r, c 값은 항상 새로운 인자에 초기화 시켜준다.
4. bfs 함수에 들어가면 방문함수와 queue를 생성했다. queue에는 좌표와 거리 값을 받는다.
5. bfs 탐색은 상하좌우와 ctrl를 눌렀을 때의 상하좌우로 탐색을 한다. 해당 카드 수와 같은 카드를 찾을 경우 value +1를 반환해준다.

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

using namespace std;

const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,-1,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 start_x = q.front().first.first;
        int start_y = q.front().first.second;
        int value = q.front().second;
        q.pop();
        if(board[start_x][start_y] == card)
        {
            board[start_x][start_y] = 0;
            r = start_x,c = start_y;
            return value+1;
        }
        for(int i=0; i<4; i++)
        {
            int nx = start_x + dx[i];
            int ny = start_y + dy[i];
            if(nx >=0 and ny >= 0 and nx < board.size() and ny < board.size() and !visited[nx][ny])
            {
                visited[nx][ny] = true;
                q.push({{nx,ny},value+1});
            }
            int nnx = start_x;
            int nny = start_y;
            while(nnx + dx[i] >=0 and nny+dy[i] >= 0 and nnx+dx[i] < board.size() and nny +dy[i] < board.size())
            {
                nnx += dx[i];
                nny += dy[i];
                if(board[nnx][nny]) break;
            }
            if(!visited[nnx][nny])
            {
                visited[nnx][nny];
                q.push({{nnx,nny},value +1});
            }
        }
    }
}
int solution(vector<vector<int>> board, int r, int c) {
    int answer = INT32_MAX;
    vector<int> card;
    for(int i=0; i< board.size(); i++)
        for(int j=0; j< board.size(); j++)
            if(board[i][j]) card.push_back(board[i][j]);
    sort(card.begin(),card.end());
    card.erase(unique(card.begin(),card.end()),card.end());
    do
    {
        vector<vector<int>> b = board;
        int rr = r, cc = c,tmp = 0;
        for(int i=0; i < card.size(); i++) tmp += bfs(b,card[i],rr,cc) + bfs(b,card[i],rr,cc);
        answer = min(answer,tmp);
    }while(next_permutation(card.begin(),card.end()));
    return answer;
}