프로그래머스 - 카드 짝 맞추기(카카오 2021 블라인드 테스트)

아놀드·2021년 7월 18일

프로그래머스

목록 보기

1/52

1. 문제

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다. 게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다. 유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

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

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

다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다. 아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.

예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.

[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회

[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회

[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회

위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.

문제
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항
board는 4 x 4 크기의 2차원 배열입니다.
board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
0은 카드가 제거된 빈 칸을 나타냅니다.
1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
r은 커서의 최초 세로(행) 위치를 의미합니다.
c는 커서의 최초 가로(열) 위치를 의미합니다.
r과 c는 0 이상 3 이하인 정수입니다.
게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.

2. 풀이

2 - 1 조건

board의 크기는 4 x 4 크기
0은 빈 칸
Ctrl + 화살표, 화살표, enter의 연산 비용은 1

2 - 2 계획

전형적인 dfs + bfs를 결합한 삼성 코테 유형의 빡센 구현 문제입니다.
처음부터 통으로 구현하기보다는
각 단계별로 나눠서 생각한 다음 차례대로 구현해봅시다.

카드 뒤집기 순서 정하기
카드는 총 A1, A2, B1, B2, C1, C2가 있다고 가정하겠습니다.
우리는 이미 카드가 어떤 위치에 있는지 알고 있기 때문에
A1을 뒤집고 B1, C2등등 짝이 맞지 않는 카드를 뒤집을 필요가 없습니다.
즉 뒤집는 순서를 강제할 수 있습니다.
이 사실을 통해 모든 카드를 뒤집으면서 구현하는 게 아닌
짝이 맞는 카드들끼리 순서대로 뒤집으며 구현할 수 있다는 깨달음을 얻을 수 있습니다.
그러면 백트래킹을 통해 순서를 생성해보겠습니다.
카드 뒤집기
카드 뒤집기 순서를 정했다면 그 순서대로 뒤집어보는 일만 남았겠죠?
대신 주의할 점이 있다면 A1, A2카드가 있을 때
A2카드를 먼저 뒤집을지, A1카드를 먼저 뒤집을지 정해줘야 합니다.
왜냐하면 A1카드를 먼저 뒤집는 비용이 A2카드를 먼저 뒤집는 비용보다 많아도
A2에서 B1 or B2카드를 뒤집는 비용이 A1에서 B1 or B2카드보다 더 적을 수도 있기 때문이죠.
카드 뒤집는 단계도 역시 백트래킹으로 구현해보겠습니다.
카드를 뒤집는 함수는
현재 좌표, 지금까지 뒤집은 비용, 지금까지 뒤집은 카드수를 인자로 받아서 구현할 수 있습니다.
카드와 카드 사이의 최단 거리 계산하기
bfs를 통해 구현합니다.
최단 거리를 계산하는 함수는
카드1의 좌표와 카드2의 좌표를 인자로 받아서 구현할 수 있습니다.

다시 총 정리를 해보면
1. 백트래킹을 통해 모든 카드 뒤집는 순서 생성
2. 순서가 생성됐을 때 각 순서쌍마다 1번을 먼저 뒤집을지 2번을 뒤집을지 정하기
3. 순서가 정해졌다면 bfs를 통해 비용을 계산
4. 모든 카드 뒤집는 순서마다 뒤집는 시뮬레이션을 마쳤다면 그 중 가장 적게 나온 비용을 리턴

3. 시간 복잡도

카드는 최대 6장이 나오니까 카드 뒤집는 순서를 생성하는 경우의 수는 6!
각 카드마다 1번을 먼저 뒤집을지, 2번을 뒤집을지 정하는 경우의 수는 2^6
카드와 카드 사이의 최단 거리를 계산하는 시간 복잡도는
총 칸 수가 4x4 = 16
각 칸 마다 최대 8개의 간선(4 + 4)이므로 (16 + 16 x 8) 144
고로 6! x 2^6 x 144 = 6,635,620 이 됩니다.

4. 전체 코드

전체 코드입니다.
주석을 참고하시면 2번 계획에서 설계한 단계대로 차례차례 구현했음을 알 수 있습니다.

function solution(board, r, c) {
    const SIZE = 4; // board의 크기 (1번 조건)
    const moves = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // 북동남서 이동 좌표
    const coordinates = {}; // 카드 번호가 key -> 카드 좌표가 value
    let cards = new Set(); // 카드 목록

    // 게임판을 돌면서 카드 좌표와 카드 목록들을 저장
    board.forEach((row, i) => row.forEach((cell, j) => {
        if (cell) {
            cards.add(cell);
            coordinates[cell] = coordinates[cell] || [];
            coordinates[cell].push([i, j]);
        }
    }));
    cards = [...cards];

    // 카드를 뒤집을 순서를 저장
    const [check, cards_permutation] = [...Array(cards.length)].reduce(m => {
        m[0].push(0);
        m[1].push(0);
        return m;
    }, [[], []]);

    // 게임판 범위내 여부
    const is_range = (y, x) => (0 <= y && y < SIZE && 0 <= x && x < SIZE);

    // 카드와 카드 사이의 최단 거리를 리턴 (3번 계획)
    const get_min_distance = (y1, x1, y2, x2) => {
        const is_arrival = (y, x) => (y == y2 && x == x2);

        // 이미 도착했을 때
        if (is_arrival(y1, x1)) return 0;

        // bfs를 통해서 최단 거리를 구함
        const q = [];
        const visit = [...Array(SIZE)].map(() => [...Array(SIZE)].map(() => 0));
        let ret = 0;

        q.push([y1, x1, 0]);
        visit[y1][x1] = 1;

        a: while (q.length) {
            const [y, x, move_count] = q.shift();

            for (const [my, mx] of moves) {
                // 화살표 이동 (한 칸)
                const ny = y + my;
                const nx = x + mx;

                // 도착하면 while문 break
                if (is_arrival(ny, nx)) {
                    ret = move_count + 1;
                    break a;
                }

                if (is_range(ny, nx) && !visit[ny][nx]) {
                    visit[ny][nx] = 1;
                    q.push([ny, nx, move_count + 1]);
                }

                // Ctrl 이동 (끝 칸)
                let ctrl_y = y;
                let ctrl_x = x;
                while (1) {
                    const tmp_y = ctrl_y + my;
                    const tmp_x = ctrl_x + mx;

                    // 범위 밖일 때
                    if (!is_range(tmp_y, tmp_x)) break;

                    ctrl_y = tmp_y;
                    ctrl_x = tmp_x;

                    // 카드를 만났을 때
                    if (board[ctrl_y][ctrl_x]) break;
                }

                // 도착하면 while문 break
                if (is_arrival(ctrl_y, ctrl_x)) {
                    ret = move_count + 1;
                    break a;
                }

                // 이미 방문했다면
                if (visit[ctrl_y][ctrl_x]) continue;
                
                visit[ctrl_y][ctrl_x] = 1;
                q.push([ctrl_y, ctrl_x, move_count + 1]);
            }
        }

        return ret;
    };

    // 백트래킹으로 카드 순서대로 뒤집어보면서 최소값 리턴 (2번 계획)
    const simulation = (y, x, cost, depth) => {
        // 기저 사례 -> 모든 카드를 뒤집었다면 비용 리턴
        if (depth == cards.length) return cost;

        // 카드
        const card = cards_permutation[depth]; 

        // 카드 좌표
        const [[ay1, ax1], [ay2, ax2]] = coordinates[card]; 

        // 현재 좌표에서 '다음 1번 카드'로 가는 비용 + '다음 1번 카드'에서 '다음 2번 카드'로 가는 비용
        const move_cost1 = get_min_distance(y, x, ay1, ax1) + get_min_distance(ay1, ax1, ay2, ax2); 

        // 현재 좌표에서 '다음 2번 카드'로 가는 비용 + '다음 2번 카드'에서 '다음 1번 카드'로 가는 비용
        const move_cost2 = get_min_distance(y, x, ay2, ax2) + get_min_distance(ay2, ax2, ay1, ax1); 

        // 뒤집음 표시
        board[ay1][ax1] = board[ay2][ax2] = 0; 

        // '다음 2번 카드'에서 그 다음 카드를 뒤집을 비용 vs '다음 1번 카드'에서 그 다음 카드를 뒤집을 비용
        // cost에 +2의 뜻은 다음 카드를 두 번 뒤집었으니 두 번의 enter연산 2를 더해줌 (3번 조건)
        const ret = Math.min(simulation(ay2, ax2, cost + move_cost1 + 2, depth + 1), simulation(ay1, ax1, cost + move_cost2 + 2, depth + 1));

        // 원래 카드 번호로 복구
        board[ay1][ax1] = board[ay2][ax2] = card; 

        return ret;
    };

    // 백트래킹을 통해 카드 순서 생성 (1번 계획)
    return (function f(depth) {
        // 기저 사례 -> 카드 순서를 생성했다면 시뮬레이션 진행
        if (depth == cards.length) return simulation(r, c, 0, 0);

        let ret = 987654321;

        for (let i = 0; i < cards.length; i++) {
            if (check[i]) continue;

            check[i] = 1;
            cards_permutation[depth] = cards[i];
            ret = Math.min(ret, f(depth + 1));
            check[i] = 0;
        }

        return ret;
    })(0);
}