[C++] 99클럽 코테 스터디 19일차 TIL + 김밥천국의 계단 (백준 28069번)

✅ 오늘의 학습 키워드

• BFS(너비 우선 탐색)

---

✅ 공부한 내용

✔️ 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/28069)

민희는 0번째 계단에서 시작하여 N번째 계단에 있는 김밥 가게에 도달하려 한다.
매번 다음의 두 가지 행동 중 하나를 선택할 수 있다.

1. 계단 한 칸을 올라간다.
2. 현재 i번 계단에서 지팡이를 두드려 i+⌊i/2⌋번 계단으로 순간이동한다.

민희는 총 K번 행동할 수 있으며, K번 이하의 행동으로 N번째 계단에 도달할 수 있는지 확인해야 한다.
(정확히 K번째 행동에서 N번째 계단에 도달한다고 되있는데 이 정확히를 조심해야 한다. K번째 가아닌 K번 이하의 행동이다.)

✔️ 풀이 로직

이 문제는 BFS(너비 우선 탐색)를 활용하여 최소 행동 횟수를 구하는 문제이다. 각 계단 위치를 노드로, 가능한 이동을 간선으로 생각하면 전형적인 그래프 탐색 문제이다. (DP로도 풀 수 있다고 한다.)

1. 0번 계단에서 시작하여 BFS로 모든 가능한 계단 위치를 탐색.
2. 각 계단에 도달하기 위한 최소 행동 횟수를 기록.
3. N번 계단에 도달하기 위한 최소 행동 횟수가 K 이하인지 확인.

 

• 초기화: visited 배열을 0으로 초기화하고, 시작 위치인 0번 계단의 값을 1로 설정한다. 이때 실제 행동 횟수는 0이지만, visited 배열에서는 미방문 상태와 구분하기 위해 1부터 시작한다.
• BFS 탐색: 큐를 사용하여 BFS를 수행한다. 각 단계에서:
  • 현재 위치에서 한 칸 위로 이동 (u + 1)
  • 현재 위치에서 지팡이를 사용하여 순간이동 (u + (u / 2))
• 방문 체크: 새로운 위치를 방문할 때마다 해당 위치까지의 최소 행동 횟수를 기록한다. 이미 방문한 위치는 다시 큐에 넣지 않아 중복 방문을 방지한다.
• 결과 판단: N번 계단에 도달하는 최소 행동 횟수(visited[N] - 1)가 K 이하인지 확인한다.

 

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떻게 해결을 했는지

처음에 나는 코드에서 visited[N] == K 조건을 사용했는데, 이 접근법에 문제가 있었다. 이 조건은 "정확히 K번 행동"으로 N에 도달해야 한다는 의미인데, 문제의 실제 요구사항은 K번 이하의 행동으로 N에 도달할 수 있는지 여부였다.

// 잘못된 접근법
if (visited[N] == K) { // 여기가 문제
    cout << "minigimbob" << endl;
} else {
    cout << "water" << endl;
}

 

또한 BFS 과정에서 아래 코드와 같이 단계 수를 K로 제한했었다. 이 제한 때문에 K보다 많은 행동으로 도달할 수 있는 경로를 무시하게 되어, 문제의 전체 탐색 공간을 커버하지 못했다.

if (next_steps <= K) {
    visited[v_up] = next_steps;
    q.push(v_up); 
}

 

해결책은 제한 없이 모든 가능한 경로를 탐색하는 BFS를 구현하고, 아래와 같이 최종적으로 N에 도달하는 최소 행동 횟수가 K 이하인지 확인하는 것이었다.

// 올바른 접근법
//visited 배열은 1부터 시작하므로 실제 단계 수는 visited[N] - 1
if (visited[N] != 0 && visited[N] - 1 <= K) { // 이렇게 바꿔야 함. 

    cout << "minigimbob" << endl;
} else {
    cout << "water" << endl;
}

- 🤩 무엇을 새롭게 알았는지

1. 문제 해석의 중요성:

• 문제에서 "정확히 K번째 행동에서 N번째 계단에 도달하면 미니김밥을 먹을 수 있습니다"라는 설명이 있었지만, 실제로는 K번 이하의 행동으로 도달할 수 있으면 되는 것이었다. (안그래도 문제 이해 잘 못하는데 하핳....😅)

2. 경로 제한의 영향: 

• 경로 탐색 시 불필요한 제한을 두면 가능한 해를 놓칠 수 있다.

---

✅ 전체 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int K; 
    cin >> N >> K;

    // 0은 방문하지 않음, 1부터 시작하는 방문 단계를 저장
    vector<int> visited(N + 1, 0);

    queue<int> q;

    visited[0] = 1;  // 0번 계단의 방문 단계를 1로 설정 (실제 단계는 0)
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); 
        q.pop();

        // 행동 1: 한 칸 올라가기
        int v_up = u + 1;
        if (v_up <= N && !visited[v_up]) {
            visited[v_up] = visited[u] + 1;
            q.push(v_up); 
        }

        // 행동 2: 지팡이 두드리기 (순간이동)
        int v_staff = u + (u / 2); 
        if (v_staff <= N && !visited[v_staff]) {
            visited[v_staff] = visited[u] + 1;
            q.push(v_staff); 
        }
    }

    // N에 도달하는 최소 단계 수가 K 이하인지 확인
    // visited 배열은 1부터 시작하므로 실제 단계 수는 visited[N] - 1
    if (visited[N] != 0 && visited[N] - 1 <= K) {
        cout << "minigimbob" << endl;
    } else {
        cout << "water" << endl;
    }

    return 0;
}