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

이 문제는 bfs와 백트래킹을 이용해서 풀었다.

 

우선 단순히 상하좌우, Ctrl + 상하좌우 총 8가지 움직임이 가능하다. visited와 같은 방문 여부 배열을 처음부터 사용할 수는 없다. 하나의 쌍을 완료한 후에 다음 최단 거리를 위해서는 이미 방문했던 위치로 또 가야할 수 있기 때문이다.

따라서 단순히 완전 탐색을 수행하면 O(8^N) 이 되므로 N이 9만 되어도 1억이 넘어가게 된다.

 

생각을 다시 해본 결과 전체 로직을 bfs로 넣을 수는 없지만, 일부 로직에서는 bfs를 적용할 수 있다는 생각을 하게 되었다. 한 점에서 단순히 다른 점으로 이동하는 데에는 bfs를 이용해서 최소 비용을 구할 수 있기 때문이다.

그래서 움직임을 담당하는 함수 minMove() 를 통해 한 점에서 다른 점으로 이동하는 최소 비용을 계산하도록 구현했다.

 

전체 로직의 경우 board[r][c] 가 0인 경우는 카드들을 순회하면서 해당 카드로 이동한다. 이 때 minMove()를 써서 비용을 먼저 구하고, solve() 를 재귀 호출하면서 다음 동작을 수행하도록 만든다.

board[r][c] 가 1 이상인 경우는 카드이므로 다른 카드 한 쪽을 목적지로 삼고 minMove()를 수행한다. 수행한 뒤에 양쪽을 모두 0으로 만들어 주고 solve() 를 재귀 호출한다.

 

위 로직을 구현하면 정답을 맞출 수 있다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;

#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3
#define INF 1000000000

vector<pair<int, int>> opposite[7];
int dy[] = {0, -1, 0, 1};
int dx[] = {-1, 0, 1, 0};

bool inRange(int y, int x) {
    if (0 <= y && y < 4 && 0 <= x && x < 4) {
        return true;
    }
    return false;
}

pair<int, int> controlMove(vector<vector<int>>& board, int y, int x, int direction) {
    int resultY = y;
    int resultX = x;
    
    switch (direction) {
        case LEFT:
            while (inRange(resultY, resultX - 1)) {
                resultX--;
                if (board[resultY][resultX] > 0) {
                    break;
                }
            }
            break;
        case UP:
            while (inRange(resultY - 1, resultX)) {
                resultY--;
                if (board[resultY][resultX] > 0) {
                    break;
                }
            }
            break;
        case RIGHT:
            while (inRange(resultY, resultX + 1)) {
                resultX++;
                if (board[resultY][resultX] > 0) {
                    break;
                }
            }
            break;
        case DOWN:
            while (inRange(resultY + 1, resultX)) {
                resultY++;
                if (board[resultY][resultX] > 0) {
                    break;
                }
            }
            break;
    }
    
    return {resultY, resultX};
}

int minMove(vector<vector<int>> board, int startY, int startX, int endY, int endX) {
    queue<pair<int, int>> q;
    vector<vector<int>> dist(4, vector<int>(4, -1));
    dist[startY][startX] = 0;
    q.push({startY, startX});
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        if (y == endY && x == endX) {
            return dist[y][x];
        }
        
        // one move
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (inRange(ny, nx) && dist[ny][nx] == -1) {
                dist[ny][nx] = dist[y][x] + 1;
                q.push({ny, nx});
            }
        }
        
        // control Move
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = controlMove(board, y, x, i);
            
            if (dist[next.first][next.second] == -1) {
                dist[next.first][next.second] = dist[y][x] + 1;
                q.push(next);
            }
        }
    }
    return -1;
}

bool isEnd(vector<vector<int>> board) {
    for (int y = 0; y < 4; y++) {
        for (int x = 0; x < 4; x++) {
            if (board[y][x] != 0) {
                return false;
            }
        }
    }
    return true;
}

pair<int, int> getOpposite(int y, int x, int myNum) {
    vector<pair<int, int>> oppo = opposite[myNum];
    for (pair<int, int>& op : oppo) {
        if (op.first == y && op.second == x) {
            continue;
        }
        return op;
    }
    return {-1, -1};
}

int solve(vector<vector<int>> board, int r, int c) {
    if (isEnd(board)) {
        return 0;
    }
    
    if (board[r][c] == 0) {
        int result = INF;
        
        for (int y = 0; y < 4; y++) {
            for (int x = 0; x < 4; x++) {
                if (board[y][x] > 0) {
                    int cost = minMove(board, r, c, y, x);
                    result = min(result, cost + solve(board, y, x));
                }
            }
        }
        return result;
    }
    
    int myNum = board[r][c];
    pair<int, int> oppo = getOpposite(r, c, myNum);
    int cost = minMove(board, r, c, oppo.first, oppo.second);
    board[r][c] = 0;
    board[oppo.first][oppo.second] = 0;
    cost += 2;
    
    return solve(board, oppo.first, oppo.second) + cost;
}

int solution(vector<vector<int>> board, int r, int c) {
    for (int y = 0; y < 4; y++) {
        for (int x = 0; x < 4; x++) {
            if (board[y][x] > 0) {
                opposite[board[y][x]].push_back({y, x});
            }
        }
    }
    
    int answer = solve(board, r, c);
    return answer;
}