[JavaScript][node.js] 백준 1327 소트 게임

문제

https://www.acmicpc.net/problem/1327

1327번: 소트 게임

풀이과정

💡 아이디어
순회는 언제 끝날까?
✅ 주어진 숫자들을 순서대로 정렬한 answer 를 구한다.
✅ 문제의 조건대로 정렬을 반복하다가 answer와 일치하는 순간 정렬 횟수를 반환 ⏩️ 최소 횟수이므로 BFS가 적합

그렇다면 방문처리는 어떻게 해야 할까?
✅ N의 최댓값이 8이므로 숫자 인덱스로 배열 방문처리를 한다면 visited[88888888] 필요
✅ 객체를 활용하면 메모리를 줄일 수 있다. 숫자 8개의 순열의 개수는 8! = 40320 이므로.

 

const answer = [...numbers].sort((a, b) => a - b).join('');
const visited = {};

1. 정답 문자열 answer
2. 방문처리 할 객체 visited

 

const bfs = (start) => {
  const queue = [];
  queue.push(start);
  visited[start[1]] = 1;
  
  /* ... */
  
}
console.log(bfs([0, numbers.join('')]));

1. queue에 들어갈 내용은 정렬 횟수인 count와, 숫자 문자열
2. 왜 문자열로 넣었을까? ⏩️ queue 안에서 진행되는 배열끼리의 비교는 O(N) 비용이 들고, 메모리도 많이 차지한다.

 

  let front = 0;
  while (front < queue.length) {
    const cur = queue[front];
    const [count, str] = cur;
    front++;

    if (answer === str) {
      return count;
    }
    
    for (let i = 0; i < n - k + 1; i++) {
      const arr = str.split('');
      for (let j = 0; j < Math.floor(k / 2); j++) {
        [arr[i + j], arr[i + k - 1 - j]] = [arr[i + k - 1 - j], arr[i + j]];
      }
      const swap = arr.join('');
      if (!visited[swap]) {
        visited[swap] = 1;
        queue.push([count + 1, swap]);
      }
    }
  }
  return -1;
};
}

1. queue가 비지 않는 동안 순회
2. 현재 문자열이 answer과 같으면 count 반환
3. 처음으로 뒤집을 숫자 for문 i로 순회. 오른쪽 k개를 뒤집어야 하므로 n-k 인덱스까지 시작 뒤집기 인덱스로 사용 가능.
4. i부터 오른쪽으로 k개의 수 뒤집기
5. 배열을 문자열로 변환, 방문확인
6. 방문하지 않은 순열이라면 방문처리 후 뒤집기 재진행. 이때 count+1

 

최종코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().trim().split('\n');
const [n, k] = input[0].split(' ').map(Number);
const numbers = input[1].split(' ').map(Number);

const answer = [...numbers].sort((a, b) => a - b).join('');
const visited = {};

const bfs = (start) => {
  const queue = [];
  queue.push(start);
  visited[start[1]] = 1;

  let front = 0;
  while (front < queue.length) {
    const cur = queue[front];
    const [count, str] = cur;
    front++;

    if (answer === str) {
      return count;
    }

    for (let i = 0; i < n - k + 1; i++) {
      const arr = str.split('');
      for (let j = 0; j < Math.floor(k / 2); j++) {
        [arr[i + j], arr[i + k - 1 - j]] = [arr[i + k - 1 - j], arr[i + j]];
      }
      const swap = arr.join('');
      if (!visited[swap]) {
        visited[swap] = 1;
        queue.push([count + 1, swap]);
      }
    }
  }
  return -1;
};

console.log(bfs([0, numbers.join('')]));

 

인사이트

• 배열의 방문처리는 문자열 key를 가진 객체를 활용할 수 있다.