BOJ 풀이 노트: 그리디와 BFS 기본기 점검
· tech
백준 1931과 2178 풀이를 문제 핵심, 접근 이유, 복잡도, 실수 포인트, 코드 핵심 라인 중심으로 정리한 실전 노트.
오늘은 서로 결이 다른 두 문제를 묶어서 풀었다. 하나는 선택의 기준을 세워 최적해를 만드는 그리디(1931), 다른 하나는 **격자 최단거리의 정석 BFS(2178)**다.
1) BOJ 1931 - 회의실 배정
문제 핵심 요약
한 개의 회의실에서 겹치지 않게 회의를 최대한 많이 배정해야 한다. 핵심은 “지금 어떤 회의를 선택해야 이후 선택 가능성이 최대가 되는가”다.
접근 아이디어(왜 이 방법인지)
종료 시간이 가장 빠른 회의를 먼저 선택하면, 남은 시간 구간을 가장 많이 확보할 수 있다.
따라서 (종료 시간 오름차순, 종료 시간이 같으면 시작 시간 오름차순) 정렬 후,
이전 회의 종료 시각보다 시작 시각이 크거나 같은 회의만 고르는 전형적인 그리디로 해결한다.
시간/공간 복잡도
- 시간:
O(N log N)(정렬) - 공간:
O(N)(회의 목록 저장)
실수하기 쉬운 포인트
- 정렬 기준을 시작 시간 우선으로 두면 최적해가 깨질 수 있다.
start >= currentEnd조건에서 등호를 빠뜨리면, 끝나는 즉시 시작 가능한 회의를 놓친다.- 입력을
(start, end)로 받지만 구현에서 비교는 종료 시각 중심이라는 점을 일관되게 유지해야 한다.
C++ 코드 설명(핵심 라인)
sort(meetings.begin(), meetings.end());pair<end, start>형태로 저장했기 때문에 기본 정렬만으로 의도한 기준이 만들어진다.
if (start >= currentEnd) {
++count;
currentEnd = end;
}- 선택 가능할 때만 카운트하고 종료 시각을 갱신한다.
다른 풀이 가능성
DP로도 상태를 정의할 수 있지만, 이 문제는 그리디 선택 성질이 성립해서 정렬+선택이 더 간단하고 빠르다.
2) BOJ 2178 - 미로 탐색
문제 핵심 요약
1(이동 가능)과 0(벽)으로 구성된 격자에서 (1,1)에서 (N,M)까지 가는 최소 칸 수를 구한다.
가중치가 모두 동일하므로 최단거리는 BFS가 정석이다.
접근 아이디어(왜 이 방법인지)
BFS는 시작점에서 거리 순으로 탐색이 진행된다.
처음 도달한 거리가 곧 최단거리이므로, dist 배열에 이전 칸 거리 + 1을 기록하며 확장하면 된다.
시간/공간 복잡도
- 시간:
O(N*M)(각 칸 최대 1회 방문) - 공간:
O(N*M)(dist+ 큐)
실수하기 쉬운 포인트
- 방문 체크를 큐에서 꺼낼 때가 아니라 넣을 때 해야 중복 삽입을 막을 수 있다.
- 입력이 문자열 형태라 문자
'0','1'비교를 해야 한다. - 시작 칸 거리 초기값을
1로 두지 않으면 출력이 한 칸씩 어긋난다.
C++ 코드 설명(핵심 라인)
dist[0][0] = 1;
q.push({0, 0});- 시작 지점 초기화. 문제 요구(지나온 칸 수) 기준을 맞추기 위해 1부터 시작한다.
if (grid[nr][nc] == '0' || dist[nr][nc] != 0) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});- 벽/기방문 칸을 제외하고, 최초 방문 시점에 거리 확정 후 큐에 넣는다.
다른 풀이 가능성
가중치가 모두 1이라 다익스트라를 쓸 이유는 없다. 만약 벽 부수기 횟수나 칸 비용이 생기면 0-1 BFS/다익스트라로 확장하는 식이 자연스럽다.
오늘의 포인트는 명확하다.
- 1931: “무엇을 기준으로 정렬해야 최적해가 보장되는가”
- 2178: “최단거리 문제에서 BFS 거리 배열을 어떻게 안정적으로 운영하는가”
기본기 문제지만, 실전에서 가장 자주 재사용되는 패턴이라 짧게라도 꾸준히 쌓아두는 게 확실히 이득이다.