seukseok의 개인 블로그

BOJ 풀이 노트: 이분 탐색 절단선과 0-1 BFS 감각 점검

· tech

오늘은 BOJ 2805와 13549를 묶어, 조건을 만족하는 최대값을 찾는 이분 탐색과 0/1 가중치 그래프에서 deque를 쓰는 0-1 BFS 구현 포인트를 실수 방지 중심으로 정리했다.

오늘은 서로 결이 다른 2문제를 선택했다.

하나는 “정답(절단기 높이)의 최대값”을 찾는 문제고, 다른 하나는 “이동 비용이 0과 1이 섞인 최단시간” 문제다. 구현 난이도보다도, 어떤 알고리즘 모델로 보는지가 핵심인 조합이었다.

1) BOJ 2805 - 나무 자르기

문제 핵심 요약

나무들의 높이가 주어질 때, 절단기 높이 H를 정해 잘라 얻는 목재 총합이 M 이상이 되도록 해야 한다. 이 조건을 만족하는 H의 최댓값을 구하는 문제다.

접근 아이디어(왜 이 방법인지)

H를 높이면 얻는 목재량은 단조 감소한다. 즉,

이 단조성 때문에 완전탐색 대신 **매개변수 탐색(이분 탐색)**이 정석이다. 탐색 중 cut >= M이면 현재 H는 가능하므로 더 큰 값을 보기 위해 오른쪽으로, 아니면 왼쪽으로 이동한다.

시간/공간 복잡도

실수하기 쉬운 포인트

C++ 코드 설명(핵심 라인)

if (cut >= M) {
    ans = mid;
    lo = mid + 1;
} else {
    hi = mid - 1;
}

가능하면 더 높은 절단 높이를 시도해야 하므로 lo = mid + 1로 밀어야 한다. 이 한 줄 방향이 문제의 본질이다.

다른 풀이 가능성

2) BOJ 13549 - 숨바꼭질 3

문제 핵심 요약

수빈이 위치 N에서 동생 위치 K로 이동한다.

최소 시간을 구해야 한다.

접근 아이디어(왜 이 방법인지)

일반 BFS는 “간선 가중치가 모두 동일”할 때만 거리 보장이 된다. 이 문제는 가중치가 0과 1로 섞여 있으므로 0-1 BFS가 맞다.

핵심은 deque 사용:

이렇게 하면 다익스트라의 우선순위 큐 없이도 거리 증가 순서를 유지할 수 있다.

시간/공간 복잡도

(여기서 V는 위치 범위 0..100000의 정점 수)

실수하기 쉬운 포인트

C++ 코드 설명(핵심 라인)

if (nx <= MAX_POS && dist[nx] > dist[cur]) {
    dist[nx] = dist[cur];
    dq.push_front(nx);
}

비용 0 이동은 같은 거리 계층이므로 덱 앞에 넣어 즉시 처리한다.

if (nx >= 0 && dist[nx] > dist[cur] + 1) {
    dist[nx] = dist[cur] + 1;
    dq.push_back(nx);
}

비용 1 이동은 뒤에 넣어 다음 거리 계층에서 처리한다.

다른 풀이 가능성

오늘 정리 포인트: