강아지는 많을수록 좋다.(백준 코딩테스트 27971번, BFS, NodeJS 풀이)

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

 

문제 수준:

실버1

 

 

문제 요약:

마법소녀 마도카의 고양이 생성(백준, 27961)에 감명받은 호무라는 자기는 강아지를 생성하기로 했다.

호무라는 N마리의 강아지를 정확히 가지고 싶다. (초과하면 안 된다.)

이를 위해 호무라가 쓸 수 있는 마법은 2가지이다.

• 강아지를 A마리 생성한다.
• 강아지를 B마리 생성한다.

그러나 강아지 마리 수가 특정 마리수 영역에 도달하면 초기화되는 버그(...)가 있다. (쉽게 버그영역이라 하겠다.)

A마리 혹은 B마리를 생성하지만 '버그 영역에 포함되는 마리 수'를 피해서 만들어야 한다.

호무라가 원하는 N마리의 강아지를 정확히 만드려면 어떻게 해야되는가?

 

 

입출력 예 (입력 / 출력):

첫 번째 줄은 이렇게 입력값이 주어진다.

'목표수 버그영역수 A마법으로생성가능한수 B마법으로생성가능한수'

 

두 번째 줄부터 나머지 줄까지는 버그영역인 곳들을 알려준다.

'버그영역시작 버그영역끝'

 

*즉 예제 입력 1번에 따르면 3~4마리일 경우 탈락이다.(강아지 생성이 초기화된다.)

 

문제 풀이 전략:

DFS로 풀려다가 BFS로 풀었다.

 

DFS 문제풀이 아이디어:

0. 최솟값을 기록할 변수를 생성한다.

1. 백트래킹 문제로 접근하여 A마리 생성과 B마리 생성하는 경우를 모두 순회하며 재귀반복을 한다.

2. N마리에 도달했을 때, 몇번 생성했는데 횟수를 최솟값 변수와 비교하여 더 적으면 최솟값을 교체한다.(N마리를 넘어버리면 그냥 return)

3. 순회 끝나면 최솟값을 알려준다.

 

목표 강아지 수가 10만마리인걸 알았다면 애초에 BFS로 접근했어야 한다. 그러나 내가 DFS밖에 못 풀던 시절이어서 DFS로 시도하였다.

 

 

BFS 문제풀이 아이디어:

1. 문제를 표현하는 그래프를 만들어 방문처리 그래프로 활용한다. (0마리 ~ N마리)

2. 버그 영역은 방문처리가 이미된 곳으로 간주하여 1로 표현한다.

3. Queue를 생성한다. (자바스크립트는 내장 Queue가 없으므로 일일이 만들어야된다. 이미 다 외웠다ㅠㅠ)

4. Queue안에 시작점인 0을 넣고, while문으로 진입한다.

5. while문 안에서 Queue에서 숫자 하나 꺼내고, 그 숫자에서 이동할 수 있는 숫자를 모두 Queue에 추가한다. (이때, 방문 처리한 곳은 못들리게 한다.)

6. 이동한 다음에 방문처리 차원에서 '지금까지 반복한 횟수(직전 visited에 기록한 수 + 1)'를 적어준다.

7. 목표 Goal에 도달하면 '지금까지 반복한 횟수(직전 visited에 기록한 수 + 1)을 출력한다. BFS는 최소 횟수를 보장하니 이게 정답이다.

 

 

횟수를 구하는 문제에서 cnt 변수를 따로 생성하지 않고 visited배열에 횟수 자체를 기입하는 방식이 있다는걸 배웠다.

이런 방식으로 순회한 다음에 visited를 console.log()로 출력해보면 아래와 같아진다.

 

순회 시작 안 했을 때 visited배열(만약 7~8이 버그 영역일 때):

// [0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

 

순회 마쳤을 때 visited배열:

// [0, 1, 1, 2, 2, 3, 3, 1, 1, 0]

 

방문 배열 자체가 이동횟수를 기록하는 역할을 한다.

 

내 풀이:

// 1차 시도 (DFS) - 시간 초과 실패
let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().trim().split("\n");

let [goal, banned, spell1, spell2] = input[0].split(" ").map(Number)
const arr = [];
const visited = new Array(goal + 1).fill().map((v) => 0); //방문처리 배열 생성
for (let i = 1; i < input.length; i++) { //버그 영역 입력값을 정제하는 반복문.
  arr.push(input[i].split(" ").map(Number));
}
arr.forEach((v) => { //버그 영역은 방문처리 미리 해주는 반복문.
  for (let i = v[0]; i <= v[1]; i++) {
    visited[i] = 1;
  }
});

let cur = 0; //현재 고양이 수
let turn = 0; // 현재 횟수
let min = 100001; //최솟값(목표가 최대 100000회니 이를 넘는 숫자를 해줌)
const path = []; // 지나온 길을 기록하는 배열

function createCats(cur, turn) {
  if (cur > goal || turn > min) return; //현재 고양이 수가 목표를 넘어서거나, 횟수가 최솟값을 이미 넘었다면 return
  if (cur === goal && turn < min) { //최솟값보다 적은 턴으로 목표에 도달했으면(성공)
    min = turn; // 최솟값을 이번 횟수로 교체
    return;
  }

  for (let i = 0; i < 2; i++) { // A마법 또는 B마법이니 경우의 수 2번 반복
    if (!visited[cur]) { // 방문 안 했으면
      visited[cur] = 1; // visited처리하고
      path.push(cur); // 방문한 루트 배열에 넣고
      createCats(cur + spell1, turn + 1); // A마법 재귀 실행
      createCats(cur + spell2, turn + 1); // B마법 재귀 실행
      visited[cur] = 0; //다 끝나면 방문 처리 풀고
      path.pop(); // 방문한 루트에서도 빼준다.
    }
  }
}

createCats(0, 0); // dfs 발동!
if (min === 100001) console.log(-1); // min값이 바뀌지 않았다면 -1 표출






//2차 시도 - (BFS) 성공
let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().trim().split("\n");

class Queue { // Queue를 class로 만듦.
  constructor() {
    this.list = {};
    this.tail = 0;
    this.head = 0;
  }
  enqueue(item) {
    this.list[this.tail] = item;
    this.tail++;
  }
  dequeue() {
    const item = this.list[this.head];
    delete this.list[this.head];
    this.head++;
    return item;
  }
  getLength() {
    return this.tail - this.head;
  }
}

let [goal, banned, spell1, spell2] = input[0].split(" ").map(Number);
let visited = new Array(goal + 1).fill().map((v) => 0); // 방문처리 배열
for (let i = 1; i <= banned; i++) {
  const [min, max] = input[i].split(" ").map(Number); //버그 영역 분리해서
  for (let j = min; j <= max; j++) {
    visited[j] = 1; // 버그 영역들은 모두 방문처리 먼저 하기
  }
}

function bfs() {
  const queue = new Queue(); // Queue 생성
  queue.enqueue(0); // 시작점 Queue에 넣기
  while (queue.getLength() !== 0) { // Queue가 다 빌 때 까지 반복
    let cur = queue.dequeue(); //Queue에서 하나 꺼내기
    if (cur === goal) return visited[cur]; // 꺼낸게 목표에 도달한거라면 visited배열에 기록된 cnt 표출
    if (cur > goal) continue; // 꺼낸게 골을 넘어선다면 continue
    for (let spelled of [cur + spell1, cur + spell2]) { // A마법, B마법 발동
      if (!visited[spelled]) { //방문 안 했으면
        visited[spelled] = visited[cur] + 1; //visited에 '전의 방문처리 숫자 + 1'를 해줌(이게 cnt임)
        queue.enqueue(spelled); //A마법, B마법 모두 Queue에 추가
      }
    }
  }
}
console.log(bfs(0) || -1); // 목표에 도달 못하면 queue가 다 빠진 경우라 undefined가 된다. 그땐 -1을 표출

대표적인 BFS문제인 숨바꼭질 문제를 실패해서 BFS 어떻게 짜는지 공부한 다음에 풀었다.

BFS에 감을 잡기 시작한 지금, 이 기세로 BFS문제를 하루에 하나씩 풀어서 재귀에 익숙해져야겠다.