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

2021 카카오 코딩 테스트 문제입니다.

 

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

문제 확인

 

배열 탐색 문제입니다. 크기가 4x4로 작으므로 dfs, 가지치기를 통해 문제를 풀 수 있습니다.

 

풀이

 

각 움직임을 dfs로 나타내면 depth와 크기가 너무 커지므로 카드 짝을 맞추는 것을 dfs, 카드 위치를 찾는 것은 queue를 이용한 bfs를 사용합니다.

상하좌우 방향으로 이동을 함을 cost 1로 두고 bfs 탐색을 통해 cost가 가장 적은 위치의 카드를 선택합니다.

카드를 선택하고 나면 같은 카드 쌍을 찾기 위해 dfs 탐색을 통해 다음으로 넘어가고 조건문을 통해 구별합니다.

 

dfs(x, y, cost, current, count)

x, y, cost : 현재 좌표, 비용

current : -1 = 가장 가까운 카드 찾기, 0 이상 = 해당 카드를 찾기

count : 현재까지 맞춘 카드 쌍

 

코드

#include <vector>
#include <cstring>
#include <queue>
using namespace std;
 
typedef struct pir {
    int first, second, cost;
    pir(int f, int s, int c) :first(f), second(s), cost(c) {};
};
int dx[] = { 1, -1, 0, 0 },
dy[] = { 0, 0, 1, -1 };
int card_count, min_val = 0x7fffffff;
 
void dfs(vector<vector<int>> &arr, int x, int y, int cost, int current, int count) {//dfs
    //current : -1 = 가장 가까운 카트 찾기, 그외 = 해당 카드 쌍 찾기
    if (cost >= min_val) return;
    if (count == card_count) {
        if (cost < min_val)min_val = cost;
        return;
    }
 
    queue<pir> next;//bfs
    bool visited[4][4] = { 0 };
    next.emplace( x, y ,0 );
    while (!next.empty()) {
        auto &cur = next.front();
        int cx = cur.first, cy = cur.second, c_cost = cur.cost, i;
        next.pop();
        if (visited[cx][cy])continue;
        visited[cx][cy] = 1;
        if (arr[cx][cy]) {
            if (current == -1) {//카드를 찾으면 카드 맞추기
                int t = arr[cx][cy];
                arr[cx][cy] = 0;
                dfs(arr, cx, cy, cost + c_cost + 1, t, count);
                arr[cx][cy] = t;
            }
 
            else if (arr[cx][cy] == current) {//카드를 맞추면 새로운 카드 찾기
                arr[cx][cy] = 0;
                dfs(arr, cx, cy, cost + c_cost + 1, -1, count + 2);
                arr[cx][cy] = current;
            }
        }
        i = cx + 1;
        if (i < 4) {//상
            for (; i < 3 && !arr[i][cy]; i++);
            if (i != cx + 1 && !visited[i][cy])next.emplace(i, cy ,c_cost + 1 );
            if (!visited[cx + 1][cy])
                next.emplace(cx + 1, cy , c_cost + 1 );
        }
        i = cx - 1;
        if (i >= 0) {//하
            for (; i > 0 && !arr[i][cy]; i--);
            if (i != cx - 1 && !visited[i][cy])next.emplace(i, cy, c_cost + 1 );
            if (!visited[cx - 1][cy])
                next.emplace( cx - 1, cy , c_cost + 1 );
        }
        i = cy + 1;
        if (i < 4) {//우
            for (; i < 3 && !arr[cx][i]; i++);
            if (i != cy + 1 && !visited[cx][i])next.emplace( cx, i , c_cost + 1 );
            if (!visited[cx][cy + 1])
                next.emplace( cx, cy + 1 , c_cost + 1 );
        }
        i = cy - 1;
        if (i >= 0) {//좌
            for (; i > 0 && !arr[cx][i]; i--);
            if (i != cy - 1 && !visited[cx][i])next.emplace( cx, i , c_cost + 1 );
            if (!visited[cx][cy - 1])
                next.emplace( cx, cy - 1, c_cost + 1 );
        }
 
    }
 
}
int solution(vector<vector<int>> arr, int x, int y) {
    vector<pair<int, int>> next;
    for (auto &i : arr)
        for (auto &j : i)
            if (j)
                card_count++;
    dfs(arr, x, y, 0, -1, 0);
    return min_val;
}
 

 

정확성 테스트

테스트 1 〉	통과 (0.10ms, 3.94MB)
테스트 2 〉	통과 (0.09ms, 3.96MB)
테스트 3 〉	통과 (0.10ms, 3.91MB)
테스트 4 〉	통과 (0.07ms, 3.95MB)
테스트 5 〉	통과 (0.40ms, 3.93MB)
테스트 6 〉	통과 (0.36ms, 3.91MB)
테스트 7 〉	통과 (0.39ms, 3.83MB)
테스트 8 〉	통과 (0.35ms, 3.93MB)
테스트 9 〉	통과 (3.15ms, 3.96MB)
테스트 10 〉	통과 (2.30ms, 3.93MB)
테스트 11 〉	통과 (2.10ms, 3.96MB)
테스트 12 〉	통과 (2.54ms, 3.75MB)
테스트 13 〉	통과 (22.99ms, 3.93MB)
테스트 14 〉	통과 (23.69ms, 3.93MB)
테스트 15 〉	통과 (15.06ms, 3.93MB)
테스트 16 〉	통과 (27.11ms, 3.95MB)
테스트 17 〉	통과 (0.01ms, 3.72MB)
테스트 18 〉	통과 (0.01ms, 3.94MB)
테스트 19 〉	통과 (0.03ms, 3.94MB)
테스트 20 〉	통과 (0.02ms, 3.89MB)
테스트 21 〉	통과 (0.43ms, 3.91MB)
테스트 22 〉	통과 (23.74ms, 3.94MB)
테스트 23 〉	통과 (22.53ms, 3.96MB)
테스트 24 〉	통과 (0.36ms, 3.9MB)
테스트 25 〉	통과 (25.20ms, 3.93MB)
테스트 26 〉	통과 (0.49ms, 3.92MB)
테스트 27 〉	통과 (0.45ms, 3.93MB)
테스트 28 〉	통과 (0.09ms, 3.93MB)
테스트 29 〉	통과 (0.08ms, 3.94MB)
테스트 30 〉	통과 (0.08ms, 3.94MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0