카드 짝 맞추기 (자바스크립트)

https://school.programmers.co.kr/learn/courses/30/lessons/72415

프로그래머스

 

• 초기 위치 => 뒤집을 수 있는 모든 카드들 위치 찾기 => 찾은 위치에서부터 같은 값을 갖고 있는 위치를 찾기 => 찾은 카드들의 갯수가 목표 갯수랑 갖기 전까지 앞의 과정 반복
•  

let answer = Number.MAX_SAFE_INTEGER;
const MAX = Number.MAX_SAFE_INTEGER;

function solution(board, r, c) {
    let T = 0;
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            if (board[i][j] !== 0) T++;
        }
    }	//찾아야 할 카드 갯수 
    
    findStartCard(board, r, c, 0, 0, T); 	// 초기 위치에서부터 출발
    return answer;
}

const ctrl = (board, x, y, i) => {		//ctrl 키를 이용해서 가장 끝 지점 or 카드 위치로 이동 하는 함수
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) return [x, y];
    if (board[nx][ny] !== 0) return [nx, ny];
    return ctrl(board, nx, ny, i);
};

const findStartCard = (board, sx, sy, moveCnt, findC, TC) => {
    if (findC === TC) {
        answer = Math.min(answer, moveCnt);
        return;
    }		// 모두 찾았다면 비교
    
    const visited = Array.from({ length: 4 }, () => [MAX, MAX, MAX, MAX]);
    visited[sx][sy] = 0;
    const q = [[sx, sy]];
    const startPoints = [];
    while (q.length) {
        const [x, y] = q.shift();
        if (board[x][y] !== 0) {
            startPoints.push([x, y, visited[x][y] + 1]);
        }
        for (let i = 0; i < 4; i++) {		// 방향키만을 이용해서 이동한 경우
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) continue;
            if (visited[nx][ny] <= visited[x][y] + 1) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push([nx, ny]);
        }
        for (let i = 0; i < 4; i++) {		//ctrl + 방향키를 이용한 경우
            const [nx, ny] = ctrl(board, x, y, i);
            if (visited[nx][ny] <= visited[x][y] + 1) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push([nx, ny]);
        }
    }
    
    //위에서 찾은 점들에서부터 타겟까지와의 거리를 구하고 재귀 함수로 다시 시작
    
    startPoints.forEach(([x, y, move]) => {
        const [ex, ey, addCnt] = findTargetCard(board, x, y);	
        const gr = [...board.map((v) => [...v])];	//각각의 경우이니 새롭게 그래프 할당
        gr[x][y] = 0;		// 뒤집은 카드는 0으로 바꿔줌
        gr[ex][ey] = 0;
        findStartCard(gr, ex, ey, moveCnt + move + addCnt, findC + 2, TC);	// 카드 2개를 찾았으니 findC+2
    });
};

const findTargetCard = (board, sx, sy) => {
    const targetValue = board[sx][sy];
    const visited = Array.from({ length: 4 }, () => [MAX, MAX, MAX, MAX]);
    visited[sx][sy] = 0;
    const q = [[sx, sy]];
    while (q.length) {
        const [x, y] = q.shift();
        if (board[x][y] === targetValue && visited[x][y] !== 0)
            return [x, y, visited[x][y] + 1];

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) continue;
            if (visited[nx][ny] <= visited[x][y] + 1) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push([nx, ny]);
        }
        for (let i = 0; i < 4; i++) {
            const [nx, ny] = ctrl(board, x, y, i);
            if (visited[nx][ny] <= visited[x][y] + 1) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push([nx, ny]);
        }
    }
};