카드 짝 맞추기

• 링크(https://programmers.co.kr/learn/courses/30/lessons/72415)

1차 시도(실패)

문제 접근

1. 카드를 순서를 정해서 지워야하니까 순열을 통해 경우의 수를 구한다.
2. 카드의 순서를 구하고 해당 순서로 최소 이동 횟수를 찾는다.
3. (r,c) 시작지점으로부터 순서에 맞게 가장 가까운 카드를 찾는다.
4. 찾은 카드는 지워주고, 카드가 지워지면 다시 시작 포인트로 잡고 순서에 맞는 가장 가까운 카드를 찾는 것을 반복한다.

문제점

• 카드가 두 장이 존재하는데, 시작지점에서부터 가장 가까운 거리에 있는 카드를 선택해도 최단거리가 아닐 수 있음.
• 이 문제점 때문에 테스트 케이스 11번이 계속 틀림.

2차 시도(성공)

문제풀이

1. 카드 순서 경우의 수를 구해준다.
2. 시작 위치에서 2가지 경우의 카드로 가는 길로 간다.
3. 해당 카드에서 같은 카드로 가서 카드를 지운다.
4. 카드가 지워진 시점에서 다시 재귀적으로 함수를 실행시킨다.(2-4 반복)

소스코드

const log = console.log;
// 라이언 1 프로도 2 어피치 3 

const permutation = (arr, str, length) => {
    return arr.reduce((acc, val, i) => {
        const newArr = [...arr];
        newArr.splice(i, 1);
        const result = permutation(newArr, str + String(val), length);
        if((str+val).length === length){
            acc.push(str+val);
        }
        acc.push(...result);
        return acc;
    }, [])
}

function solution(board, r, c) {
    const cards = getCards(board);
    const cardLen = cards.length;
    let res = [Infinity];
    const ps = permutation(cards, "", cardLen);
    
    for(const p of ps){
        const order = [...p].map(e => +e);
        const newBoard = board.map(e => [...e]);
        getAnswer(newBoard, r, c, order, 0, res);    
    }
    
    return res[0] + cardLen*2;
}

function getAnswer(board, r, c, order, total, res){
    if(order.length === 0){
        res[0] = Math.min(res[0], total);
        return;
    };
    const card = order.shift();
    const firsts = findCard(board, r, c, card);
    
    firsts.forEach(e => {
        const [row, col, count] = e;
        board[row][col] = 0;
        const [row2, col2, count2] = findCard(board, row, col, card)[0];
        board[row2][col2] = 0;
        getAnswer(board, row2, col2, [...order], total+count+count2, res);
        board[row][col] = card;
        board[row2][col2] = card;
    });
}

function findCard(board, r, c, card){
    const n = board.length;
    let result = [];
    const visited = Array.from(Array(n), () => Array(n).fill(0));
    const coords = [[r, c, 0]];
    
    while(coords.length){
        const [row, col, count] = coords.shift();
        if(board[row][col] === card){
            result.push([row, col, count]);
        };
        visited[row][col] = 1;
        const temp = getCoords(board, row, col, count, visited);
        temp.forEach(([row, col]) => visited[row][col] = 1); 
        coords.push(...temp);
    }
    return result;
}

function getCoords(board, r, c, count, visited){
    const n = board.length;
    const coords = [];
    const dr = [1,-1,0,0];
    const dc = [0,0,1,-1];
    
    for(let i=0 ; i<4 ; i++){
        const row = r+dr[i];
        const col = c+dc[i];
        
        if(col < 0 || row < 0 || col >= n || row >= n 
           ||  visited[row][col] === 1) continue;
        coords.push([row, col, count+1]);
    }
    
    const cntl = [
        cntlUp(board,r,c),
        cntlDown(board,r,c),
        cntlLeft(board,r,c),
        cntlRight(board,r,c)
    ];
    cntl.forEach((p) => {
        const [row, col, d] = p;
        if(visited[row][col] === 1 || dupCheck(coords, [row, col])) return;
        coords.push([row, col, d+count]);
    });
    
    return coords;
}

function dupCheck(arrs, point){
    return arrs.some((e) => e[0] === point[0] && e[1] === point[1]);
}

function cntlUp(board, r, c){
    if(r === 0) return [0, c, 0];
    for(let i=r-1 ; i>0 ; i--){
        if(board[i][c] !== 0) return [i, c, 1];
    }
    return [0, c, 1];
}

function cntlDown(board, r, c){ 
    const n = board.length;
    if(r === n-1) return [n-1, c, 0]
    for(let i=r+1 ; i<n ; i++){
        if(board[i][c] !== 0) return [i, c, 1];
    }
    return [n-1, c, 1];
}

function cntlLeft(board, r, c){ 
    if(c === 0) return [r, 0, 0]
    for(let i=c-1 ; i>0 ; i--){
        if(board[r][i] !== 0) return [r, i, 1];
    }
    return [r, 0, 1];
}

function cntlRight(board, r, c){
    const n = board.length;
    if(c === n-1) return [r, n-1, 0];
    for(let i=c+1 ; i<n ; i++){
        if(board[r][i] !== 0) return [r, i, 1];
    }
    return [r, n-1, 1];
}

function getCards(board){
    const n = board.length;
    const set = new Set();
    for(let r=0 ; r<n; r++){
        for(let c=0 ; c<n ; c++){
            if(board[r][c] !== 0) set.add(board[r][c]);
        }
    }
    return [...set];
}