99클럽 코테 스터디 18일차 TIL - 강아지는 많을수록 좋다 (BFS/DP)

Hyejin·2025년 4월 23일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99Club

목록 보기

19/21

문제: https://www.acmicpc.net/problem/27971
알고리즘 분류: 너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

문제 정의

호무라는 정확히 N마리의 강아지를 키우고 싶습니다.
두 가지 마법을 사용할 수 있습니다: A마리 또는 B마리의 강아지를 생성하는 마법
제약 사항: 특정 닫힌 구간 [L,R]에 해당하는 수의 강아지가 만들어지면 모두 사라집니다.
처음에는 강아지가 0마리 있습니다.
최소 행동 횟수로 정확히 N마리를 만들어야 합니다.

문제 접근 방식

최단 경로 문제 → BFS

0부터 N까지의 강아지 수를 노드로 생각하고, A마리나 B마리를 추가하는 것을 간선으로 볼 수 있다.
제약 구간에 포함되는 상태는 갈 수 없는 노드이다.
BFS(너비 우선 탐색)를 사용하여 최소 행동 횟수를 찾을 수 있다:
- 초기 상태는 0마리에서 시작
- 각 상태에서 A마리 또는 B마리를 추가했을 때의 새로운 상태를 검사
- 제약 구간에 포함되는 상태는 방문하지 않음
- N마리에 도달하면 해당 시점의 행동 횟수가 답

내 코드

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M, A, B] = input[0].split(' ').map(Number);

// 제약 구간
const restrictedRanges = [];
for (let i = 1; i <= M; i++) {
    const [L, R] = input[i].split(' ').map(Number);
    restrictedRanges.push([L, R]);
}

// 특정 수가 제약 구간에 포함되는지 검사
const isRestricted = (num) => {
    for (const [L, R] of restrictedRanges) {
        if (num >= L && num <= R) {
            return true;
        }
    }
    return false;
}

// BFS로 최소 행동 횟수 계산
const findMinActions = () => {
    // N이 제약 구간에 포함되면 불가능
    if (isRestricted(N)) {
        return -1;
    }

    // 방문 배열 (각 강아지 수에 도달하기 위한 최소 행동 횟수 저장)
    const visited = new Array(N + 1).fill(-1);
    visited[0] = 0; // 초기 상태: 0마리

    // BFS를 위한 큐
    const queue = [0];

    while (queue.length > 0) {
        const current = queue.shift();
        
        // N에 도달했으면 최소 행동 횟수 반환
        if (current === N) {
            return visited[current];
        }

        // A마리 추가하는 경우
        const addA = current + A;
        if (addA <= N && !isRestricted(addA) && visited[addA] === -1) {
            visited[addA] = visited[current] + 1;
            queue.push(addA);
        }

        // B마리 추가하는 경우
        const addB = current + B;
        if (addB <= N && !isRestricted(addB) && visited[addB] === -1) {
            visited[addB] = visited[current] + 1;
            queue.push(addB);
        }
    }

    // N에 도달할 수 없는 경우
    return -1;
}

console.log(findMinActions());