[Programmers] 카드 짝 맞추기

문제

 

2021 KAKAO BLIND RECRUITMENT > 카드 짝 맞추기

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

 

 

아이디어

 

해당 문제를 처음 접했을 때 어떻게 풀지 막막했었습니다.

 

여러 생각을 하던 도중 아이디어가 생각나지 않아 질문하기 메뉴를 통해 아이디어를 찾다가 순열을 이용하신 분이 있는 것을 보고 어떻게 풀어내야 할지 아이디어가 생각난 문제였습니다.

 

코드는 짧지 않지만 풀이법은 생각보다 간단했습니다.

 

탐색할 카드들을 순열을 통해 순서를 정하고 키 조작 횟수를 최소화하며 순서대로 카드를 찾아 가기만 하면 끝이었습니다.

 

해당 아이디어를 기반으로 다음과 같은 알고리즘 로직으로 코드를 구현했습니다.

 

1. board의 원소들 중 가장 큰 인덱스 값 찾기(=카드 쌍의 개수)

2. 존재하는 카드 쌍의 개수만큼 순열 구하기

3. 현재 위치에서 다음에 뒤집을 카드 탐색 

4. 다음에 해당하는 최소 키 조작 횟수를 BFS를 이용하여 구하기

 - 현재 위치 → 다음 뒤집을 첫 번째 카드 → 다음 뒤집을 두 번째 카드

 - 현재 위치 → 다음 뒤집을 두 번째 카드 → 다음 뒤집을 첫 번째 카드

5. DFS를 이용하여 3~4를 최대 깊이 까지 탐색

6. 탐색되어 나온 최솟값(=움직이기 위한 조작 횟수)과 카드 개수x2(=카드 뒤집는 조작 횟수)를 더하여 결괏값으로 리턴

 

 

구현 코드 (JavaScript)

 

const dirj = [1, 0, -1, 0]; // j방향
const diri = [0, 1, 0, -1]; // i방향
let res = Number.MAX_VALUE;

class Node { // 현재 위치와 키 조작 카운트를 담은 클래스
    constructor(i, j, count) {
        this.i = i;
        this.j = j;
        this.count = count;
    }
}

const getPath = (board, starti, startj, endi, endj) => { // 이동을 위환 최소 키 조작 횟수 구하기
    const queue = []
    const visited = Array.from(Array(4), () => new Array(4).fill(false)); // 방문여부 체크

    queue.push(new Node(starti, startj, 0));

    while(queue.length !== 0) {
        const node = queue.shift();

        if(visited[node.i][node.j]) {
            continue;
        }

        if(node.i === endi && node.j === endj) { // BFS로 탐색했기 때문에 처음 목적에 도착했을 때 count값이 최솟값
            return node.count;
        }

        visited[node.i][node.j] = true;

        for(let a=0; a<4; a++) { // 다음으로 갈 4방향 순회
            let nexti = node.i + diri[a];
            let nextj = node.j + dirj[a];

            if(nexti >= 4 || nexti < 0 || nextj >= 4 || nextj < 0 || visited[nexti][nextj]) {
                continue;
            }

            queue.push(new Node(nexti, nextj, node.count+1));
        }

        for(let a=0; a<4; a++) { // 다음으로 갈 4방향을 Ctrl을 이용하여 순회
            let nexti = node.i + diri[a];
            let nextj = node.j + dirj[a];

            while(nexti < 4 && nexti >= 0 && nextj < 4 && nextj >= 0 && board[nexti][nextj] === 0) {
                nexti = nexti + diri[a];
                nextj = nextj + dirj[a];
            }

            if(nexti >= 4 || nexti < 0 || nextj >= 4 || nextj < 0) { // 배열을 벗어났을 경우에는 이전으로 되돌아가기
                nexti = nexti - diri[a];
                nextj = nextj - dirj[a];
            }

            if(visited[nexti][nextj]) {
                continue;
            }

            queue.push(new Node(nexti, nextj, node.count+1));
        }
    }
}

const solve = (board, starti, startj, middlei, middlej, endi, endj, targetIndex, array, count) => { // 최소 키 조작 횟수를 구하며 DFS 탐색
    if(targetIndex >= array.length) { // 모든 카드를 탐색했을 경우
        res = Math.min(res, count);
        return;
    }

    count = count + getPath(board, starti, startj, middlei, middlej); // [starti, startj]에서 [middlei, middlej]까지 가는 최솟값
    board[middlei][middlej] = 0; // 카드 제거

    count = count + getPath(board, middlei, middlej, endi, endj); // [middlei, middlej]에서 [endi, endj]까지 가는 최솟값
    board[endi][endj] = 0; // 카드 제거

    const next = [];

    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board.length; j++) {
            if(board[i][j] === array[targetIndex+1]) { // 다음으로 뒤집을 카드 인덱스의 위치 구하기
                next.push(i);
                next.push(j);
            }
        }
    }

    const tempBoard = Array.from(Array(4), () => new Array(4));
    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board.length; j++) {
            tempBoard[i][j] = board[i][j];
        }
    }

    solve(tempBoard, endi, endj, next[0], next[1], next[2], next[3], targetIndex+1, array, count);

    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board.length; j++) {
            tempBoard[i][j] = board[i][j];
        }
    }

    solve(tempBoard, endi, endj, next[2], next[3], next[0], next[1], targetIndex+1, array, count);
}

const makeP = (board, r, c, index, array) => { // 순열
    if(index >= array.length) {
        const next = [];

        for(let i=0; i<board.length; i++) {
            for(let j=0; j<board.length; j++) {
                if(board[i][j] === array[0]) { // 순열로 구해진 array의 첫 번재 원소값에 해당하는 카드 인덱스 위치 구하기
                    next.push(i);
                    next.push(j);
                }
            }
        }

        const tempBoard = Array.from(Array(4), () => new Array(4)); // 배열의 현재상태를 보존하기 위해 임시 배열 생성
        for(let i=0; i<board.length; i++) {
            for(let j=0; j<board.length; j++) {
                tempBoard[i][j] = board[i][j];
            }
        }

        solve(tempBoard, r, c, next[0], next[1], next[2], next[3], 0, array, 0); // 첫 번째로 찾은 카드의 위치를 탐색 후 두 번째로 찾은 카드의 위치를 탐색

        for(let i=0; i<board.length; i++) {
            for(let j=0; j<board.length; j++) {
                tempBoard[i][j] = board[i][j];
            }
        }
        solve(tempBoard, r, c, next[2], next[3], next[0], next[1], 0, array, 0); // 두 번째로 찾은 카드의 위치를 탐색 후 첫 번째로 찾은 카드의 위치를 탐색
        return;
    }

    for(let i=index; i<array.length; i++) {
        let temp = array[index];
        array[index] = array[i];
        array[i] = temp;

        makeP(board, r, c, index+1, array);

        temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

function solution(board, r, c) {
    let n = 0; // 카드 총 개수

    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board.length; j++) {
            n = Math.max(n, board[i][j]);
        }
    }

    const array = []; // 카드 인덱스를 담는 배열
    for(let i=1; i<=n; i++) {
        array.push(i);
    }

    makeP(board, r, c, 0, array);

    return res + n*2;
}

 

 

 

읽어주셔서 감사합니다.