[프로그래머스] LV.3 카드 짝 맞추기 (JS)

KG·2021년 5월 3일
BFSBacktrackingLv.3순열알고리즘카카오프로그래머스
2

알고리즘

목록 보기
39/61
post-thumbnail

문제

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

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

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

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

현재 카드가 놓인 상태를 나타내는 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) 입니다.

입출력 예시

boardrcresult
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]1014
[[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]0116

풀이

2021 카카오 블라인드 테스트에서 출제된 문제이다. 작년에 공개된 문제라는 점을 감안해도 정답자 수가 제일 적은 편에 속하는 문제인데 그만큼 난이도가 다른 Lv.3 문제들에 비해 비교적 높은 편인 것 같다. 무엇보다 어마어마한 지문의 양이 선뜻 문제를 풀어볼까 하는 의지를 많이 무너뜨리는 까닭 역시 있는 듯 하다. 차근차근 한 단계씩 문제를 풀어가며 구현해보자.

카드 위치 좌표 연결 리스트

먼저 주어지는 게임보드의 크기는 4x4 고정이며 주어지는 카드 역시 제한 조건에 따르면 1부터 6까지 총 6종류이다. (문제 설명에서는 8가지로 되어있는데 제한 조건에 따르면 6종류이다. 딱히 문제 풀이에 큰 장애가 되진 않으니 그냥 넘어가도 상관없다)

따라서 먼저 동일한 그림들이 게임보드 어디 좌표에 위치하고 있는지에 대한 연결 리스트를 먼저 생성해주자. 밑에서 자세히 설명하겠지만 최단 경로를 찾는 것과 같기에 그래프 탐색 알고리즘을 이용할 것이기 때문이다.

연결 리스트는 객체(Object)를 사용해도 좋고 배열을 사용해도 좋지만 여기서는 ES6에서 등장한 Map 자료구조를 사용해서 만들어주려 한다. 굳이 해당 자료형을 쓰는 특별한 이유는 없다. 본인에게 더 편한 방법이 있다면 해당 방식으로 구현해주어도 좋다.

// 카드캐릭터 : [ 좌표1, 좌표2 ] 의 형태로 저장할 것
const card_pos = new Map();

// 4x4의 크기이므로 해당 크기만큼 중첩 반복
for(let i = 0; i < 4; i++) {
  for(let j = 0; j < 4; j++) {
    // 해당 좌표의 값이 있다면 카드가 있다는 의미
    if(board[i][j]) {
      // 현재 좌표에서의 카드 캐릭터 번호를 구하고
      const card = board[i][j];
      // 이미 그 카드값을 저장한 적 있다면
      if(card_pos.has(card)) {
        // 카드값의 기존 value(배열)을 구해서
        const origin = card_pos.get(card);
        // 카드값을 갱신
        card_pos.set(card, [...origin, [i, j]]);
      } else {
        // 카드값을 처음 저장하는 경우엔 바로 좌표값 저장
        card_pos.set(card, [ [i, j] ]);
      }
    }
  }
}

위의 과정을 통하면 우리는 각 주어진 캐릭터가 게임 보드에서 위치하고 있는 좌표 2개씩을 얻을 수 있다. 따라서 해당 좌표를 통해 우리는 최단 경로를 찾아줄 것 이다.

순열

본격적으로 문제에서 요구하는 최단 경로를 찾아주기 전에 순열을 구해야 한다. 갑자기 왜 순열을 구해야 하는 것 일까?

핵심은 어떤 카드에서 시작하느냐에 따라 제 각각 다른 최단 경로가 나올 수 있기 때문이다. 문제에서 요구하는 최소 횟수는 카드를 모두 제거하는 경우에서의 조작 최솟값이고, 카드를 제거하기 위해서는 동일한 카드를 연달아 선택해야 한다. 따라서 만약 [1, 2, 3]과 같이 3종류의 카드가 있었다면, 몇 번의 카드 부터 시작하느냐에 따라 생성되는 최단 경로가 모두 다르고 그에 따른 조작 횟수 역시 다르기 때문이다.

즉 어떤 카드부터 방문하는지에 따라 최종 최솟값의 결과가 달라질 수 있기 때문에 이러한 순서를 모두 고려하는 순열 알고리즘이 필요한 것이다. 따라서 우리는 위에서 구해준 카드 좌표 연결 리스트에서 키 값(카드 캐릭터)을 대상으로 키 값의 개수 만큼의 순열(= nPn = n!)을 구해주자. 그리고 구해준 순열의 순서대로 반복문을 돌면서 최단 경로를 계산해주면 될 것 이다.

순열을 구하는 알고리즘은 해당 포스트에서 설명한 바가 있기에 자세한 설명은 생략한다. 최대값이 문제 조건에 따라 6이고 6! = 720 가지이므로 모든 순열 목록을 구하는데 시간 부담이 없다.

// arr = 카드의 캐릭터 종류, n = 카드 캐릭터의 개수
// 즉 n! 의 목록을 구하는 것과 동일
const getPermutation = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

최단 경로와 최소 조작 횟수

최소 조작값을 구하는 것은 결국 각 캐릭터 간 최단 경로를 구하는 것과 같다. 가장 적게 움직이는 것이 최소 조작에 제일 가까운 값이기 때문이다. 문제에서 주어진 보드는 2차원 배열이기 때문에 각 좌표값을 노드로 생각하여 접근하면 그래프 알고리즘으로 최단 경로를 구할 수 있다. 보통 최단 경로 계산을 위해 BFS 탐색 알고리즘을 많이 사용하므로 우리도 BFS 알고리즘을 구현하여 최소 조작 횟수를 구해주도록 하자.

다만 해당 문제에서 단순히 최단 경로가 최소 조작 횟수가 되는 것이 아니다. 왜냐하면 문제에서 제시하는 커맨드에 따라 단 한 번의 조작으로 여러 경로를 단숨에 뛰어넘을 수 있기 때문이다(crtl + 방향키). 때문에 단순히 좌표 값의 거리 차이로만 경로를 계산하는 것이 아니라, 문제에서 주어진 커맨드 값을 모두 고려한 최단 경로를 계산해 주어야 한다. 문제에서 주어진 커맨드는 다음과 같이 크게 3가지이다.

  1. 각 방향키 1칸 이동 => 1회
  2. ctrl + 방향키 이동 => 1회
  3. 엔터 => 1회

이때 1번과 3번은 기존 BFS 탐색 알고리즘 내부 로직에서도 카운트를 증가시키는 등의 방법으로 간단하게 계산이 가능하다. 그러나 2번의 경우에는 누른 방향키의 방향에서 가장 가까운 카드로 한 번에 이동하는 매커니즘이 작용하므로 이 부분을 계산해주기 위해 따로 함수로 만들어주자. 또한 게임보드의 좌표 크기는 4x4 이므로 해당 공간 내부에서만 조작이 가능하도록 체크하는 함수 역시 만들어주자.

// 이동하려는 좌표가 공간 내부인지 점검하는 함수
// 내부에 있다면 true, 벗어나는 경우 false 반환
const isMovable = (y, x) => {
  if(-1 < y && y < 4 && -1 < x && x < 4) return true;
  else return false;
}

// ctrl + 방향키 이동
// 입력된 방향과 가장 가까이 있는 카드 좌표 반환
const ctrl_move = (y, x, dy, dx, board) => {
  // x, y는 현재 카드의 좌표, dx, dy는 이동 방향
  let ny = y, nx = x;
  while (true) {
    // 따라서 nnx, nny는 이동방향이 적용된 후 좌표
    const nny = ny + dy;
    const nnx = nx + dx;
    // 해당 이동방향으로 갈 수 없다면 현재 좌표 반환
    if(!isMovable(nny, nnx)) return [ny, nx];
    // 이동 방향 좌표에 카드가 있다면 해당 좌표 반환
    if(board[nny][nnx]) return [nny, nnx];
    // 카드가 없는 경우 동일한 방향으로 계속 진행해야 하므로
    // 현재 좌표값을 이동방향이 적용된 좌표로 갱신 후
    // 다음 계산에 이용하며 계속 진행
    ny = nny;
    nx = nnx;
  }
}

다음은 위에서 구현해 준 두 개의 함수를 이용하여 BFS 탐색 함수 역시 만들어주자. 해당 함수는 외부에 독립적으로 만들어줄 것이기 때문에 관련된 정보를 모두 인자로 받아오게끔 설계했다. 따라서 현재 커서의 위치인 시작좌표(sx, sy)와 카드 캐릭터가 각각 위치한 종료좌표(ex, ey)를 받고 계산을 위해 전체 게임 보드(board) 역시 인자로 전달받도록 하자.

const searchCard_bfs = (sy, sx, ey, ex, board) => {
  // 시작과 종료좌표가 같으면 바로 탐색을 종료할 수 있다.
  // 이 경우 현재 커서위치가 찾고자 하는 카드 바로위에 위치한 경우이다.
  if(sy === ey && sx === ex) return [sy, ex, 1];
  
  // BFS 탐색을 위한 queue 선언
  const queue = [];
  // 조작 횟수를 저장할 table 선언, board의 크기와 동일
  // 따라서 table[y][x] 값으로 현재 카드값에 접근 가능
  // 다음에 이동할 좌표에 현재 좌표 값 + 1 을 통해
  // 조작 횟수 저장 가능
  const table = new Array(4).fill().map(_ => new Array(4).fill(0));
  // 방문 여부 체크를 위한 배열 선언
  const visit = new Array(4).fill().map(_ => new Array(4).fill(false));
  
  // 상하좌우 이동방향 좌표값
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  
  // BFS 탐색을 위한 준비
  queue.push([sy, sx]);
  visit[sy][sx] = true;
  
  while(queue.length) {
    const [y, x] = queue.shift();
    
    // dx, dy 값에 따라 상하좌우 이동을 위한 반복
    for(let i = 0; i < 4; i++) {
      // ny, nx는 매 반복마다 상하좌우로 이동한 후 좌표
      let ny = y + dy[i];
      let nx = x + dx[i];
      
      // 해당 좌표로 이동이 가능하고
      if(isMovable(ny, nx)) {
        // 아직 해당 좌표에 방문을 하지 않았다면
        if(!visit[ny][nx]) {
          // 해당 좌표 방문체크 후
          visit[ny][nx] = true;
          // 해당 좌표 값을 이전 좌표 값+1로 갱신
          // 이는 이전 좌표에서 해당 좌표로 이동하는데 소요된 1번의 조작횟수를 의미
          table[ny][nx] = table[y][x]+1;
          
          // 만약 이동한 좌표가 도착지점과 같다면
          if(ny === ey && nx === ex)
            // 좌표값과 해당좌표까지의 조작횟수+1을 반환 후 종료
            // +1을 하는 이유는 엔터를 눌러 뒤집기 때문
            return [ny, nx, table[ny][nx]+1];
          
          // 조건에 만족하지 않는 다면 계속 BFS 탐색
          queue.push([ny, nx]);
        }
      }
      
      // 위에서는 상하좌우 1칸씩 이동하는 경우를 체크
      // 이번엔 ctrl + 방향키 좌표를 적용
      [ny, nx] = ctrl_move(y, x, dy[i], dx[i], board);
      
      // ctrl_move는 항상 공간 범위를 벗어나지 않으니
      // 별도로 이동이 가능한지 isMovable로 체크할 필요 없음
      // 나머지 로직은 위와 동일
      if(!visit[ny][nx]) {
        visit[ny][nx] = true;
        table[ny][nx] = table[y][x]+1;
        
        if(ny === ey && nx === ex)
          return [ny, nx, table[ny][nx]+1];
        
        queue.push([ny, nx]);
      }
    }
  }
  
  // BFS 함수를 다 돌았음에도 조작횟수를 리턴하지 못했다면
  // 가능한 도달 경로가 없다는 것과 같으므로
  // 시작좌표와 무한대의 값을 리턴
  return [sy, sx, Infinity];
}

위에서 구현한 BFS 함수를 앞서 구한 순열 값에 따른 좌표를 각각 반복하여 카드 간의 최소 경로를 구해줄 수 있을 것 이다. 하지만 위 함수만으로는 최소 조작 횟수를 정확히 계산할 수 없다. 다음 과정에서 그 이유와 해결 방안을 같이 살펴보자.

백트랙킹으로 최소 조작 횟수 계산

위에서 구현한 BFS 함수로는 최상의 조건에서 각 카드간의 최소 조작 횟수를 문제없이 구할 수 있다. 여기서 최상의 조건이란 두 카드 사이에 어떤 장애물도 없고 주어진 커맨드로 접근이 가능한 경우를 말한다. 그러나 모든 카드들이 이와 같은 조건에 위치할 수는 없다. 예시로 주어진 입력값을 보아도 그림을 보면 어피치의 경우엔 초기 상태에서 어떠한 경우로도 제거가 불가능한 것을 확인할 수 있다.

또한 커서의 위치는 무작위로 r과 c의 좌표로 주어진다. 만약 커서의 위치가 방문해야할 카드위에 있지 않고 그 사이 어딘가에 있다고 가정해보자. 그렇다면 커서의 입장에서는 A카드를 먼저 방문 후 B카드를 방문하는 방법과, B카드를 먼저 방문 후 A카드를 방문하는 방법이 존재한다. 이때 각각의 최단 경로가 무엇이 더 작을 지 모르기 때문에 이를 각각 수행해야 한다.

이때 방문하는 카드는 뒤집어주기 때문에, 어떤 방법을 먼저 택하든 후자의 경우엔 이미 뒤집힌 상태의 게임보드에서 탐색을 해야하므로 정확한 탐색이 이루어질 수 없다. 따라서 DFS 탐색 알고리즘에서의 backtracking을 이용해 먼저 방문 후 계산을 마치고 해당 카드를 다시 원상태로 복구할 필요가 있다. 때문에 위에서 구현한 BFS 탐색 알고리즘을 다시 DFS 로직 내부에서 백 트랙킹을 이용하여 구현해야 한다. 이에 대한 로직은 크게 다음과 같다.

  1. 현재 차례의 순열에서 카드 캐릭터를 하나씩 가져옴
  2. 가져온 카드를 바탕으로 해당 카드의 두 개 좌표를 구함
  3. 두 개 좌표 중 하나를 먼저 BFS 탐색으로 방문하여 최단 경로 및 조작 횟수 계산
  4. 해당 카드를 뒤집고 DFS 탐색 실시
  5. DFS 탐색이 끝나면 뒤집은 카드를 다시 원복
  6. 위에서 먼저 방문한 좌표 외에 나머지 좌표를 다시 BFS 탐색으로 방문하여 최단 경로 및 조작 횟수 계산
  7. 해당 카드를 뒤집고 DFS 탐색 실시
  8. DFS 탐색이 끝나면 뒤집은 카드를 다시 원복
  9. 현재 차례의 순열에서 모든 캐릭터를 선택했다면 기존의 최소값과 현재 최소값을 비교하여 최소값 갱신

즉 위에서 먼저 구현한 BFS 탐색 알고리즘은 3번과 6번에서 각각 두번 수행할 것이고, 이들이 끝나고 반환한 값을 이용하여 백트랙킹을 이용해 DFS 탐색을 재귀 호출 방식으로 구현할 것이다. DFS 탐색은 현재 차례의 순열에서 각 순열의 원소값을 모두 사용할 때까지 반복한다. 따라서 각 카드 캐릭터를 모두 시작값으로 반복을 시작하여 해당 경우에서의 최소값을 구하고 이 중에서 가장 작은 최소값을 리턴하도록 하는 것이다.

해당 함수 역시 메인 함수 외부에 선언할 것이므로 필요한 정보를 모두 인자로 전달받도록 설계했다. 문제에서 주어진 커서의 위치를 (sy, sx)로 전달받고 기존에 구한 순열의 크기만큼 반복문을 돌 것 이기에 이에 대한 값을 (k, m)으로 전달받는다. k는 0부터 시작하여 DFS 재귀 호출마다 값을 1씩 늘려가며 현재 차례의 순열의 원소들을 탐색할 것이고 m은 외부에서 도는 순열의 크기 인덱스 i를 전달받는다. 또한 최소 조작 횟수 계산을 위한 count를 전달해 DFS의 deps를 통해 횟수 계산을 하도록 하자. 그리고 나머지 계산을 위해 필요한 card_pos와 permutaion 역시 전달해주자. 또한 게임 보드 board 역시 필요한데 배열에서 조작이 일어나기 때문에 원본 배열 유지(Immutable)를 위해 복사본 new_board 역시 전달해주자. 마지막으로 최소값 갱신을 위해 전역변수 answer를 선언하여 접근하도록 했다. 초기 answer의 값은 Infinity로 초기화하여 최소값을 만날 때 최소값으로 갱신하도록 했다.

// 전역변수로 선언
let answer = Infinity;

...

// 방문한 카드를 뒤집는 함수
const remove = (card, board, card_pos) => {
  // 방문한 카드의 좌표값을 구하고
  // 해당 좌표값을 0으로 변경 => 뒤집음
  for(const [y, x] of card_pos.get(card))
    board[y][x] = 0;
}

// 뒤집은 카드를 다시 원복하는 함수 (백트랙킹을 위해)
const restore = (card, board, card_pos) => {
  // 방문한 카드의 좌표값을 구하고
  // 해당 좌표값을 카드값으로 변경 => 다시 뒤집어 원복
  for(const [y, x] of card_pos.get(card))
    board[y][x] = card;
}

const searchMin_backtrack = (sy, sx, k, m, count, board, card_pos, permutation) => {
  // k는 현재 순열(1차원 배열)에서 각 원소의 인덱스
  // 따라서 카드 캐릭터 종류의 수와 동일하게 되는 시점은
  // 현재 순열을 모두 하나씩 방문 완료했다는 뜻이므로
  // 현재 count와 기존 answer 중 최솟값을 비교해 갱신
  // 재귀 함수 탈출 조건
  if(k === [...card_pos.keys()].length) {
    answer = Math.min(answer, count);
    return;
  }
  
  // 현재 선택한 카드 캐릭터
  // k는 DFS deps로 값이 변하고, m은 외부 반복문에 의해 영향
  // 따라서 DFS가 진행됨에 따라 현재 차례 순열의 원소들을 차례로 방문
  const card = permutation[m][k];
  // 선택한 카드가 위치한 두 개 좌표를 구해줌
  const [ly, lx] = [card_pos.get(card)[0][0], card_pos.get(card)[0][1]];
  const [ry, rx] = [card_pos.get(card)[1][0], card_pos.get(card)[1][1]];
  
  // 현재 커서 (sy, sx)에서 카드의 (ly, lx) 좌표 선 방문 후 해당 위치에서 다시 (ry, rx) 좌표 방문
  // 이때 res1 + res2가 최소 조작 횟수가 됨
  let [ny1, nx1, res1] = searchCard_bfs(sy, sx, ly, lx, board);
  let [ny2, nx2, res2] = searchCard_bfs(ny1, nx1, ry, rx, board);
  
  // 위에서 선택한 카드를 뒤집고
  remove(card, board, card_pos);
  // 위에서 방문을 마친 좌표(ny2, nx2)를 커서의 위치로 하여 재귀호출
  // deps가 1만큼 깊어지므로 k+1, 횟수는 count += res1 + res2
  searchMin_backtrack(ny2, nx2, k+1, m, count + res1 + res2, board, card_pos, permutation);
  // 재귀 호출이 끝나면 원상 복구
  // 호출이 끝나는 시점은 현재 차례의 순열의 모든 원소를 방문 완료한 시점
  restore(card, board, card_pos);
  
  // 현재 커서 (sy, sx)에서 카드의 (ry, rx) 좌표 방문 후 해당 위치에서 다시 (ly, lx) 좌표 방문
  [ny1, nx1, res1] = searchCard_bfs(sy, sx, ry, rx, board);
  [ny2, nx2, res2] = searchCard_bfs(ny1, nx1, ly, lx, board);
  
  // 위의 로직과 동일
  remove(card, board, card_pos);
  searchMin_backtrack(ny2, nx2, k+1, m, count + res1 + res2, board, card_pos, permutation);
  restore(card, board, card_pos);
}

정답 리턴

위에서 backtracking을 활용한 DFS 탐색 역시 구현을 마쳤으므로, 메인 함수에서 해당 함수를 호출하여 정답을 계산해주자. 앞에서 설명했든 구해준 순열을 바탕으로 반복문을 돌려, 순열의 현재 인덱스를 인자로 전달해주면 될 것 이다.

// 카드의 캐릭터 종류(배열)과 그 크기를 인자로 전달
// n! 과 동일
const permutation = getPermutation([...card_pos.keys()], card_pos.size);

// 원본 배열 유지를 위한 복사본 전달
// 통과를 위해서 굳이 필요한 작업은 아니다!
const new_board = board.slice();
for(let i = 0; i < permutation.length; i++) {
  // 현재 커서의 좌표 r, c
  // 첫 원소부터 접근하기 위한 0, 현재 순열의 인덱스 i
  // 초기 count = 0
  searchMin_backtrack(r, c, 0, i, 0, new_board, card_pos, permutation);
}

return answer;

전체코드

코드량이 많은 만큼 구현력도 요구하는 동시에 BFS + DFS + backtracking의 개념을 모두 이해하고 있어야 접근이 가능한 문제였던 것 같다. 각각은 크게 어려운 개념과 알고리즘은 아니지만 이를 혼합하여 접근해야 했기에 다소 어렵게 느껴진 감이 있는 것 같다. 주석을 제외한 전체 코드는 다음과 같다.

let answer = Infinity;

function solution (board, r, c) {
  const new_board = board.slice();
  const card_pos = new Map();
  
  for(let i = 0; i < 4; i++) {
    for(let j = 0; j < 4; j++) {
      if(board[i][j]) {
        const card = board[i][j];
        if(card_pos.has(card)) {
          const origin = card_pos.get(card);
          card_pos.set(card, [...origin, [i, j] ]);
        } else {
          card_pos.set(card, [ [i, j] ]);
        }
      }
    }
  }
  
  const permutation = getPermutation([...card_pos.keys()], card_pos.size);
  
  for(let i = 0; i < permutation.length; i++) {
    searchMin_backtrack(r, c, 0, i, 0, new_board, card_pos, permutation);
  }
  
  return answer;
}

const isMovable = (y, x) => {
  if(-1 < y && y < 4 && -1 < x && x < 4) return true;
  else return false;
}

const ctrl_move = (y, x, dy, dx, board) => {
  let ny = y, nx = x;
  
  while(true) {
    const nny = ny + dy;
    const nnx = nx + dx;
    if(!isMovable(nny, nnx)) return [ny, nx];
    if(board[nny][nnx]) return [nny, nnx];
    ny = nny;
    nx = nnx;
  }
}

const searchCard_bfs = (sy, sx, ey, ex, board) => {
  if(sy === ey && sx === ex) return [sy, sx, 1];
  
  const queue = [];
  const table = new Array(4).fill().map(_ => new Array(4).fill(0));
  const visit = new Array(4).fill().map(_ => new Array(4).fill(false));
  
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, 1, -1];
  
  queue.push([sy, sx]);
  visit[sy][sx] = true;
  
  while(queue.length) {
    const [y, x] = queue.shift();
    
    for(let i = 0; i < 4; i++) {
      let ny = y + dy[i];
      let nx = x + dx[i];
      
      if(isMovable(ny, nx)) {
        if(!visit[ny][nx]) {
          visit[ny][nx] = true;
          table[ny][nx] = table[y][x] + 1;
          
          if(ny === ey && nx === ex)
            return [ny, nx, table[ny][nx]+1];
          
          queue.push([ny, nx]);
        }
      }
      
      [ny, nx] = ctrl_move(y, x, dy[i], dx[i], board);
      
      if(!visit[ny][nx]) {
        visit[ny][nx] = true;
        table[ny][nx] = table[y][x] + 1;
        
        if(ny === ey && nx === ex)
          return [ny, nx, table[ny][nx]+1];
        
        queue.push([ny, nx]);
      }
    }
  }
  
  return [sy, sx, Infinity];
}

const remove = (card, board, card_pos) => {
  for(const [y, x] of card_pos.get(card))
    board[y][x] = 0;
}

const restore = (card, board, card_pos) => {
  for(const [y, x] of card_pos.get(card))
    board[y][x] = card;
}

const searchMin_backtrack = (sy, sx, k, m, count, board, card_pos, permutation) => {
  if(k === [...card_pos.keys()].length) {
    answer = Math.min(answer, count);
    return;
  }
  
  const card = permutation[m][k];
  const [ly, lx] = [card_pos.get(card)[0][0], card_pos.get(card)[0][1]];
  const [ry, rx] = [card_pos.get(card)[1][0], card_pos.get(card)[1][1]];
  
  let [ny1, nx1, res1] = searchCard_bfs(sy, sx, ly, lx, board);
  let [ny2, nx2, res2] = searchCard_bfs(ny1, nx1, ry, rx, board);
  
  remove(card, board, card_pos);
  searchMin_backtrack(ny2, nx2, k+1, m, count + res1 + res2, board, card_pos, permutation);
  restore(card, board, card_pos);
  
  [ny1, nx1, res1] = searchCard_bfs(sy, sx, ry, rx, board);
  [ny2, nx2, res2] = searchCard_bfs(ny1, nx1, ly, lx, board);
  
  remove(card, board, card_pos);
  searchMin_backtrack(ny2, nx2, k+1, m, count + res1 + res2, board, card_pos, permutation);
  restore(card, board, card_pos);
}

const getPermutation = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

출처

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

profile
KG
개발잘하고싶다
이전 포스트

[프로그래머스] LV.3 불량 사용자 (JS)

다음 포스트

[프로그래머스] LV.3 보석 쇼핑 (JS)

0개의 댓글