BOJ 풀이 노트: 주유 그리디와 플로이드 워셜 기본기 점검
· tech
BOJ 13305와 11404를 묶어, 선형 스캔 기반 그리디와 3중 루프 기반 Floyd-Warshall 구현에서 자주 틀리는 포인트와 코드 핵심 라인을 간단명료하게 정리했다.
오늘은 그리디 1문제 + 그래프 최단경로 1문제로 유형을 분리해서 풀었다.
- BOJ 13305 - 주유소
- BOJ 11404 - 플로이드
하나는 “지금까지 본 최소 가격”을 유지하는 누적 최적화, 다른 하나는 “경유지 k를 허용하면서 거리 갱신”하는 전형적인 DP 형태라 사고 방식이 완전히 다르다. 하루 2문제 루틴에서 기본기 점검용으로 균형이 좋았다.
1) BOJ 13305 - 주유소
문제 핵심 요약
도시를 왼쪽에서 오른쪽으로 이동할 때, 각 도시의 주유 가격과 도시 사이 거리 정보가 주어진다. 목적지까지 가는 총 비용의 최솟값을 구하는 문제다.
접근 아이디어(왜 이 방법인지)
핵심은 “미래를 정확히 몰라도 현재까지의 최저 가격으로 다음 구간을 사는 것이 항상 이득”이라는 점이다.
왼쪽부터 순회하면서:
minCost= 지금까지 등장한 최소 리터당 가격- 다음 도로 길이만큼
minCost * dist[i]를 더함
이렇게 하면 매 구간에서 최선의 선택이 전역 최적해로 이어진다(그리디 성립).
시간/공간 복잡도
- 시간:
O(N) - 공간:
O(N)(입력 저장 기준)
실수하기 쉬운 포인트
- 비용 누적을
int로 처리해 오버플로우 나는 실수 (long long필수) - 현재 도시 가격으로 최소값 갱신 타이밍을 잘못 잡는 실수
- 마지막 도시는 이동 구간이 없다는 점을 놓치는 실수
C++ 코드 설명(핵심 라인)
minCost = min(minCost, cost[i]);
answer += minCost * dist[i];현재 구간을 지나기 전에 최저 단가를 갱신하고, 그 단가로 해당 구간 연료 비용을 누적한다.
다른 풀이 가능성
- 별도 자료구조 없이 선형 스캔이 가장 단순/안정적이다.
- 문제 구조상 우선순위 큐나 DP를 쓰는 방식은 가능해도 과한 설계가 되기 쉽다.
2) BOJ 11404 - 플로이드
문제 핵심 요약
도시 수 N, 버스 노선 정보가 주어질 때 모든 도시 쌍 (i, j)의 최소 이동 비용을 출력하는 문제다. 경로가 없으면 0을 출력한다.
접근 아이디어(왜 이 방법인지)
모든 쌍 최단거리는 Floyd-Warshall이 정석이다.
dist[i][j]를 초기화한 뒤, 경유지 k를 1부터 N까지 허용하면서
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])를 반복하면 된다.
N이 크지 않은 범위라 O(N^3)이 충분히 통과 가능하고 구현도 직관적이다.
시간/공간 복잡도
- 시간:
O(N^3) - 공간:
O(N^2)
실수하기 쉬운 포인트
- 같은
(a, b)간선이 여러 번 들어올 때 최소값으로 초기화하지 않는 실수 INF + INF연산으로 오버플로우/오염이 발생하는 실수(가드 필요)- 도달 불가능한 경우를 0으로 출력해야 한다는 출력 조건 누락
C++ 코드 설명(핵심 라인)
dist[a][b] = min(dist[a][b], c);중복 간선 입력이 가능하므로 초기 입력부터 최소 간선비용만 유지한다.
if (dist[i][k] == INF || dist[k][j] == INF) continue;
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);연결되지 않은 상태를 건너뛰어 잘못된 덧셈을 방지한다.
다른 풀이 가능성
- 각 정점에서 다익스트라를
N번 수행하는 방법도 있다. - 다만 이 문제 조건에서는 Floyd-Warshall이 구현량 대비 안정적이고, 정답 행렬 출력 요구와도 궁합이 좋다.
오늘 정리 포인트:
- 그리디 문제는 “무엇을 상태로 유지할지”(여기선 지금까지 최저 가격)만 잘 잡으면 코드가 매우 간결해진다.
- Floyd-Warshall은 점화식 자체보다 초기화/INF 처리/출력 형식을 더 자주 틀린다.
내일도 그래프/DP/그리디를 섞어 2문제 루틴을 이어갈 예정이다.