[프로그래머스] 72415 카드 짝 맞추기 - 자바스크립트

문제

프로그래머스

 

알고리즘 & 자료구조

• 완전 탐색 (Brute Force) - 순열
• BFS
• 비트 마스킹 (Bit Masking)

 

로직

아래 유튜브 영상을 참고하여 코드를 작성했습니다.

너무 어려워서 스스로의 힘으로 해결하지 못했거든요..😅

 

 

먼저 존재하는 카드 값에 따른 비트 마스킹을 수행합니다.

• 예를 들어, 1부터 3까지의 카드가 있다면 1111(15)이 되겠죠. (0의 비트는 기본으로 1로 설정합니다)
• 이때 비트 1을 카드가 제거된 상태로 정의하여, 카드 제거시 해당 비트를 1로 변환하고 모든 카드 값에 대한 비트가 모두 1이면(미리 비트 마스킹해둔 값과 같으면) 정답을 반환합니다.

 

어떤 값의 카드를 먼저 제거할 것인지 순열에 따른 모든 순서를 탐색합니다.

• 같은 값의 두 카드 A, B가 있을때 A → B, B → A 순서 모두 수행해야 합니다.
• 순서에 따른 출발지와 다음 목적지에 대해 BFS를 실시합니다.
  • 큐에 키 조작 횟수를 함께 담아 업데이트하며, 목적지에 도착시 해당 조작 횟수를 반환합니다.
• 재귀적으로 순열에 따른 모든 순서에 대한 BFS를 실시하면 되겠죠.

 

코드

⏱ 시간 복잡도 : O(n!)

function solution(board, r, c) {
  const bfs = (removed, src, dst) => {
    const isOutOfBounds = (x, y) => {
      return x < 0 || x > 3 || y < 0 || y > 3;
    };

    const di = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = Array.from(Array(4), () => Array(4).fill(false));
    const queue = [[...src, 0]];

    while (queue.length) {
      const [x, y, cnt] = queue.shift();
      if (x === dst[0] && y === dst[1]) {
        return cnt;
      }
      // 상, 하, 좌, 우 이동
      for (const [dx, dy] of di) {
        let [nx, ny] = [x + dx, y + dy];

        if (isOutOfBounds(nx, ny)) {
          continue;
        }

        if (!visited[nx][ny]) {
          visited[nx][ny] = true;
          queue.push([nx, ny, cnt + 1]);
        }

        // [Ctrl] 키 누르기
        // - 이미 한칸 이동했으므로 최대 2칸 이동 가능
        for (let i = 0; i < 2; i++) {
          // 카드가 존재
          if (!(removed & (1 << board[nx][ny]))) {
            break;
          }
          // 커서가 더이상 이동 불가
          if (isOutOfBounds(nx + dx, ny + dy)) {
            break;
          }
          [nx, ny] = [nx + dx, ny + dy];
        }

        if (!visited[nx][ny]) {
          visited[nx][ny] = true;
          queue.push([nx, ny, cnt + 1]);
        }
      }
    }

    return Infinity;
  };

  const permutate = (cnt, removed, src) => {
    // 모든 카드 제거
    if (removed === allRemoved) {
      answer = Math.min(answer, cnt);
      return;
    }

    for (const [card, pos] of cardPos.entries()) {
      // 이미 제거한 카드
      if (removed & (1 << card)) {
        continue;
      }

      const one = bfs(removed, src, pos[0]) + bfs(removed, pos[0], pos[1]) + 2;
      const two = bfs(removed, src, pos[1]) + bfs(removed, pos[1], pos[0]) + 2;

      permutate(cnt + one, removed | (1 << card), pos[1]);
      permutate(cnt + two, removed | (1 << card), pos[0]);
    }
  };

  const cardPos = new Map();
  let allRemoved = 1;
  let answer = Infinity;

  board.forEach((row, x) => {
    row.forEach((card, y) => {
      if (!card) {
        return;
      }
      if (cardPos.has(card)) {
        cardPos.get(card).push([x, y]);
        return;
      }
      cardPos.set(card, [[x, y]]);
      // 카드 값에 대한 비트 마스킹
      // - 비트 1이면 제거됨을 의미
      allRemoved |= 1 << card;
    });
  });

  permutate(0, 1, [r, c]);

  return answer;
}

 

리뷰

처음에는 모든 이동(한칸 이동, [Ctrl] 이동)에 대한 BFS를 수행하며, 매 이동시의 board 상태 + 커서 위치 + 뒤집은 카드 위치 문자열을 Set에 넣어 방문 여부를 제어했다.

하지면 자꾸만 틀렸다.. (아직도 틀린 원인을 모르겠다)

결국 해결하지 못하여 해당 문제에 대한 풀이 영상을 참고하여 순열과 비트 마스킹을 이용했다.

요근래 푼 문제 중에 가장 오래걸렸고 힘들었다 😂