99클럽 코테 스터디 18일차 TIL - 강아지는 많을수록 좋다(백준 27971번)

오늘의 학습 키워드

• BFS (너비 우선 탐색)
• 탐색
• 금지된 구간 처리
• 제약 조건 처리
• 최단 거리

---

공부한 내용 정리

 

오늘 문제는 마법소녀 호무라가 강아지를 N마리 만들기 위해 두 가지 마법(A, B 생성 마법)을 사용하는데, 처음에는 강아지 수 0에서 시작해 +A 또는 +B를 반복하며이는 BFS로 상태를 탐색하면 되는 전형적인 최단 거리 문제였습니다.

• 현재 강아지 수가 금지된 구간에 포함되면 해당 상태는 방문 불가
• 강아지 수가 N을 초과하지 않도록 하며, 0부터 N까지 탐색
• BFS를 통해 +A, +B 연산을 상태 그래프처럼 탐색하며 최소 횟수를 찾음

주요 조건 :

• 정확히 N에 도달하는 가장 빠른 행동 횟수(최소 연산 수) 를 구하는 문제로, 특정 금지된 개수 구간(닫힌 구간)에 들어가면 지금까지 키운 강아지가 전부 사라진다.

---

소스코드

import java.util.*;
import java.io.*;

public class Main {
    public static Queue<int[]> queue;
    public static boolean[] visited;
    public static boolean[] forbidden;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 목표 강아지 수
        int m = Integer.parseInt(st.nextToken()); // 금지 구간 수
        int a = Integer.parseInt(st.nextToken()); // A 마법: +a 마리
        int b = Integer.parseInt(st.nextToken()); // B 마법: +b 마리

        visited = new boolean[n + 1];   // 강아지 수가 0~n까지므로 n+1
        forbidden = new boolean[n + 1]; // 금지 구간 여부를 저장

        // 금지 구간 입력 처리
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            for (int j = x; j <= y; j++) {
                forbidden[j] = true;
            }
        }

        queue = new LinkedList<>();
        queue.add(new int[]{0, 0});  // 시작 상태: 강아지 0마리, 행동 횟수 0
        visited[0] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int count = curr[0]; // 현재 강아지 수
            int step = curr[1];  // 현재까지의 행동 횟수

            // 목표에 도달한 경우
            if (count == n) {
                System.out.println(step);
                return;
            }

            // 가능한 다음 상태: A 또는 B 마법 사용
            for (int next : new int[]{count + a, count + b}) {
                // 조건: 범위 안, 방문하지 않았고, 금지 구간이 아닌 상태만 허용
                if (next <= n && !visited[next] && !forbidden[next]) {
                    visited[next] = true;
                    queue.add(new int[]{next, step + 1});
                }
            }
        }

        // 목표에 도달하지 못한 경우
        System.out.println(-1);
    }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

어제 DFS에 대해 공부해서 처음엔 DFS로 고민하고, 금지 구간을 리스트로 처리하려 했지만, 효율성과 편의를 위해 boolean[] forbidden을 활용했습니다.
“최소 행동 횟수”가 핵심이기 때문에 최단 거리 탐색이 가능한 BFS를 활용해야 한다는걸 알았습니다.

 

• 어떻게 해결했는지

queue에 현재 상태와 횟수를 함께 저장하면서 방문 체크와 금지 구간 체크를 동시에 하도록 하였습니다..
조건에 맞는 경우에만 다음 상태로 전이하도록 구성했고, 방문 체크 금지 구간 체크를 동시에 하였습니다.

 

• 무엇을 새롭게 알았는지

BFS 문제에서 상태가 숫자 하나일 때는 1차원 visited 배열로도 충분히 해결 가능하다는 점

금지 구간을 boolean 배열로 미리 처리하면 훨씬 빠르게 탐색이 가능하다는 점

BFS는 “모든 경우의 수를 빠르게 탐색해 최적해를 찾는 문제”에 적합하다는 걸 느꼈습니다.

 

• 내일 학습할 것은 무엇인지

BFS의 기본 문제를 더 풀어서 BFS를 익숙하게 해야겠습니다. 그리고 조건이 많은 BFS를 풀어봐야겠습니다. 특히 최단거리 문제, 최소 비용, 조건 기반 경로 탐색같이 다양한 조건의 문제를 도전해봐야겠습니다.

---