[Algorithm] Programmers :: 카드 짝 맞추기

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

프로그래머스

struct Node
{
    int y;
    int x;
    int count;
};
 
vector<vector<Node>> cards(7);
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[5][5] = { false };
vector<int> permutation;
 
int BFS(int startY, int startX, int destY, int destX, bool type, vector<vector<int>>& board)
{
    if (startY == destY && startX == destX) return 0;
 
    memset(visited, false, sizeof(visited));
 
    queue<Node> q;
    q.push({ startY, startX, 0});
    visited[startY][startX] = true;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        q.pop();
 
        if (curY == destY && curX == destX)
        {
            if (type)
            {
                board[startY][startX] = 0;
                board[destY][destX] = 0;
                return curCount + 2;
            }
            else return curCount;
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY == 4) continue;
            if (nextX < 0 || nextX == 4) continue;
            if (visited[nextY][nextX]) continue;
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX, curCount + 1 });
        }
 
        for (int i = 0; i < 4; ++i) // 끝까지 반복이동.
        {
            int tempCurY = curY;
            int tempCurX = curX;
 
            while (1)
            {
                int nextY = tempCurY + dir[i][0];
                int nextX = tempCurX + dir[i][1];
 
                if (nextY < 0 || nextY == 4) break;
                if (nextX < 0 || nextX == 4) break;
                
                tempCurY = nextY;
                tempCurX = nextX;
 
                if (board[tempCurY][tempCurX] != 0) break;
            }
 
            if (visited[tempCurY][tempCurX]) continue;
 
            visited[tempCurY][tempCurX] = true;
            q.push({ tempCurY,tempCurX,curCount + 1 });
        }
    }
}
 
int maxCount = 0;
 
int DFS(int startY, int startX, int permuIndex, int sum, vector<vector<int>>& board)
{
    if (permuIndex == maxCount) return sum;
 
    int num = permutation[permuIndex];
    vector<vector<int>> tempBoard = board;
 
    int first = BFS(startY, startX, cards[num][0].y, cards[num][0].x, false, tempBoard);
    first += BFS(cards[num][0].y, cards[num][0].x, cards[num][1].y, cards[num][1].x, true, tempBoard);
    first = DFS(cards[num][1].y, cards[num][1].x, permuIndex+1, first, tempBoard);
    tempBoard = board;
 
    int second = BFS(startY, startX, cards[num][1].y, cards[num][1].x, false, tempBoard);
    second += BFS(cards[num][1].y, cards[num][1].x, cards[num][0].y, cards[num][0].x, true, tempBoard);
    second = DFS(cards[num][0].y, cards[num][0].x, permuIndex+1, second, tempBoard);
 
    return sum + min(first, second);
}
 
int solution(vector<vector<int>> board, int r, int c)
{
    int answer = 0x3f3f3f3f;
 
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[i].size(); ++j)
        {
            if (board[i][j] != 0)
            {
                cards[board[i][j]].push_back({ i,j });
            }
        }
    }
    
    for (int i = 0; i < cards.size(); ++i)
    {
        if (cards[i].size() > 0)
        {
            permutation.push_back(i);
        }
    }
 
    maxCount = permutation.size();
 
    do
    {
        if (permutation[0] == 2 && permutation[1] == 3 && permutation[2] == 1)
        {
            int asdf = 0;
        }
        int startY = r;
        int startX = c;
        int num = permutation[0];
 
        int minResult = 0x3f3f3f3f;
        
        vector<vector<int>> tempBoard = board;
 
        int first = BFS(startY, startX, cards[num][0].y, cards[num][0].x, false, tempBoard);
        first += BFS(cards[num][0].y, cards[num][0].x, cards[num][1].y, cards[num][1].x, true, tempBoard);
        first = DFS(cards[num][1].y, cards[num][1].x, 1, first, tempBoard);
 
        tempBoard = board;
 
        int second = BFS(startY, startX, cards[num][1].y, cards[num][1].x, false, tempBoard);
        second += BFS(cards[num][1].y, cards[num][1].x, cards[num][0].y, cards[num][0].x, true, tempBoard);
        second = DFS(cards[num][0].y, cards[num][0].x, 1, second, tempBoard);
        
        minResult = min(first, second);
 
        answer = min(answer, minResult);
 
    } while (next_permutation(permutation.begin(), permutation.end()));
    
    return answer;
}

 

출발위치는 반드시 카드가 있는곳인 줄 알고 코드를 작성했다가 아닌걸 깨닫고 다시 처음부터 작성했었다.

방문할 카드의 순서를 수열로 구해야하는데 next_permutation으로 수열을 먼저 구했다.

이후 현재위치에서 해당카드까지 이동 후, 해당카드의 짝에 맞는곳으로 이동하면서 최소값을 구했다.

 

중요한것은 완전탐색을 해야한다는 것이다. 

나같은 경우 처음에 풀이할 때 현재위치에서 특정숫자카드를 찾아갈 때, 한쌍인 두개의 카드중 가까운 카드를 먼저 찾아가고 그다음 짝이되는 카드를 찾는식으로 했다가 테스트케이스 11번만 실패가 뜨길래 많이 헤맸었다.

딱 한개만 틀리는거라서 그냥 조금만 수정하면 될 줄 알았는데 다른사람들의 글을 보아하니 가까운카드가 아닌 멀리있는 카드를 먼저 찾아갈 때 최소값이 나오는 경우가 존재한다는 걸 알았다(완전탐색해야한다는 뜻)

 

그래서 DFS로 한쌍인 두개의 카드를 각각 탐색해서 모든 경우의 수를 구해주었다.

첫번째카드를 탐색한 후, 두번째 카드를 탐색하기전에 board를 다시 원래대로 돌려줘야 하는것을 잊지말자.