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

오늘의 학습 키워드

• BFS
• 상태 제한
• 시간 초과 / 메모리 초과 이슈 대응
• 경로 최적화

---

공부한 내용 정리

문제는 0번 계단에서 시작해서 K번의 행동만으로 정확히 N번 계단에 도달할 수 있는지 판단하는 문제였어요.
행동은 2가지입니다:

• +1 계단 오르기
• +floor(i/2) 만큼 순간이동

처음엔 단순한 DFS나 배열 기반 BFS로 접근했지만,
K가 최대 1,000,000이라는 점, 그리고 방문 수 체크를 무한하게 하면 메모리 초과가 발생한다는 점에서 고비를 맞았어요.

그래서 전략을 다음과 같이 바꿨어요:

• 상태는 현재 위치(cur)와 행동 횟수(cnt[cur])로 구성
• BFS 탐색에서 cnt[다음 위치]를 방문 여부 판단 기준으로 사용
• 중복 방문 방지를 위해 cnt[] 배열을 사용하고, 거리 업데이트 방식으로 최적화

---

소스코드

/*
입력:
    - 계단 N개
    - 계단을 오르는 횟수 K 100만
조건:
    - 0번 계단에서 시작
    - 택 1 행동가능
        1. 계단을 1칸 올라감
        2. i + floor(i/2)로 순간이동.
    - 처음엔 무조건 1칸 올라가야됨
    - 2번째 부터 선택.
로직:
    - K번의 행동으로 N번 계단에 도달해야됨.
    - 완전탐색 > 뭘로 탐색?
        - DFS? 배열 길이를 100만으로 하면 되나? 안될거같다.
        - BFS? 깊이 제한을 둔다면?
    - visited 가 100만 이면 메모리 초과.
        - 이걸 해시 셋으로 대체
출력:
    - N개의 계단을 K번 만에 올라갈 수 있니?
    - 있으면 minigimbob 없으면 water
 */
import java.io.*;
import java.util.*;

public class Main {
    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 k = Integer.parseInt(st.nextToken());

        // 큐를 다 돌았는데 못 도달했다. 그럼 실패인거
        System.out.println(bfs(n, k) ? "minigimbob" : "water");
    }

    public static boolean bfs(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        // 0번 계단에서 시작
        queue.add(0);
        int[] cnt = new int[n + 1];

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            // 정확히 K번 행동하고, 정확히 N번 해서 도달
            if(cur == n && cnt[cur] <= k){
                return true;
            }

            // 더 행동 할 수 없으면
            if(cnt[cur] == k){
                continue;
            }

            // 1번 1칸 올라가
            int walk = cur + 1;
            if(walk <= n && cnt[walk] == 0){
                cnt[walk] = cnt[cur] + 1;
                queue.add(walk);
            }

            // 2번 순간이동
            int jump = cur + cur/2;
            if(jump <= n && cnt[jump] == 0){
                cnt[jump] = cnt[cur] + 1;
                queue.add(jump);
            }
        }

        return false;
    }
}

---

오늘의 회고

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

처음에는 boolean[] visited로 방문 체크했더니 메모리 초과.
그 다음엔 visited 없이 단순 큐 기반으로 구현했더니 시간 초과.
특히, cnt[] 없이 무한 방문이 발생하며 중복 상태가 생겨서 처리 속도가 늦어짐....

 

• 어떻게 해결했는지

cnt[] 배열을 선언하여 각 위치에 도달한 횟수를 기록했고,

이미 더 적은 횟수로 도달한 곳이라면 재방문하지 않도록 조건 처리했습니다.

BFS의 특성을 살려 먼저 도달한 경우가 최단 거리임을 활용하여 불필요한 경로는 가지 않도록 구성했습니다.

 

 

 

• 무엇을 새롭게 알았는지

상태 공간이 크거나 제한적이지 않은 경우, 방문 배열을 무작정 키우면 안 된다는 걸 체감했고

조건을 정확히 파악하고 방문 기준을 현재 depth로 처리하는 게 중요하다는 걸 다시금 느꼈어요.

실제 제한(cnt[cur] == k)을 넘지 않게 잘 제어하는 것도 중요한 포인트였어요.

근데 아직도 이거 100%이해한건 아닌 것 같아요. 한 10%정도가 이해가 안가는 부분이 있어요.

 

 

 

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

내일 이 문제를 한번 더 풀어봐야겠어요. 너무 오랜 시간을 써서 더 이상은 봐도 모르겠네요..

---