[TIL] 2026-07-02 — 코딩테스트 3제: BFS 두 문제와 이벤트 시뮬레이션 (보물섬·그림·NBA 농구)
코딩테스트 시험으로 세 문제를 풀었다. 백준 2589 보물섬, 1926 그림, 2852 NBA 농구. 앞의 둘은 격자 BFS인데 성격이 정반대였고, 마지막은 순수 이벤트 시뮬레이션이었다. 세 문제를 한 자리에서 풀면서 “BFS를 여러 번 부를 때 상태를 리셋해야 하는가”의 기준과 “시뮬레이션에서 상태 갱신의 순서”를 확실히 정리했다.
오늘 한 일 요약
- 보물섬 (2589) — 모든 육지 칸을 시작점으로 BFS를 돌려 “최단거리의 최댓값”을 구했다. 미방문(0)과 거리(0)의 충돌을 +1 인코딩으로 피하고, 시작점마다
memset으로 dist를 리셋했다. - 그림 (1926) — flood fill BFS로 연결 요소의 개수와 최대 크기를 동시에 구했다. 컴포넌트끼리 겹치지 않아
visited리셋이 필요 없다는 점을 보물섬과 대비해 정리했다. - NBA 농구 (2852) — 골 이벤트 사이 구간을 통째로 정산하는 이벤트 시뮬레이션. “적립 먼저, 스코어 갱신 나중”의 순서와 경기 종료(48:00) 잔여 구간 정산이 핵심이었다.
1. 보물섬 (백준 2589) — 다중 시작 BFS + 매번 리셋
문제 재진술
L/W 격자에서 육지 두 칸을 골랐을 때의 최단거리 중, 가장 긴 값을 찾는다. “최단거리들의 최댓값”이라는 게 포인트다.
접근을 잡기까지
“가장 긴 시간이 걸리는 두 곳”이라는 문장만 보고 순간 최장 경로(가장 길게 걷는 길)를 떠올렸는데, 다시 읽으니 아니었다. 두 지점 사이는 어디까지나 최단거리로 이동하고, 그 최단거리가 가장 큰 쌍을 찾는 거다. 최장 경로였으면 일반 그래프에서 다항 시간에 못 푸는 문제라 뭔가 이상하다 싶었는데, 최단거리 최댓값이면 얘기가 완전히 달라진다.
브루트포스는 “모든 육지 쌍마다 최단거리 계산”인데, BFS는 시작점 하나에서 모든 칸까지의 최단거리를 한 번에 준다. 쌍마다 돌 이유가 없고, 시작점마다 한 번씩만 돌면 된다. 가중치가 전부 1이니 다익스트라까지 갈 것도 없이 BFS로 충분하다. 시작점이 정해져 있지 않으니 모든 육지를 시작점으로 BFS를 돌린다. 비용은 육지 최대 2500칸 × BFS 한 번 O(2500) ≈ 625만 연산으로 1초 제한에 여유 있다.
핵심 아이디어
모든 육지에서 BFS를 돌리고, 그때그때 나온 최단거리들의 전체 최댓값이 답.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n, m, ans;
string a[54];
int dist[54][54];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int bfs(int sy, int sx)
{
memset(dist, 0, sizeof(dist));
queue<pair<int, int>> q;
dist[sy][sx] = 1;
q.push({ sy, sx });
int ret = 1;
while (!q.empty()) {
int y = q.front().first, x = q.front().second;
q.pop();
ret = max(ret, dist[y][x]);
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (a[ny][nx] != 'L' || dist[ny][nx]) continue;
dist[ny][nx] = dist[y][x] + 1;
q.push({ ny, nx });
}
}
return ret - 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j] == 'L')
ans = max(ans, bfs(i, j));
cout << ans << endl;
return 0;
}
막힌 점·실수
- 미방문 0과 거리 0 충돌. 시작점의 거리를 0으로 두면 “아직 안 간 칸”과 구분이 안 된다. 시작점을 1로 놓는 +1 인코딩으로 가고, 반환할 때
ret - 1로 되돌렸다.dist[ny][nx]가 0이 아니면 방문한 것으로 판정하는 게 한 줄로 끝나서 깔끔하다. - BFS를 여러 번 부르니 매 호출 memset 리셋. 처음 한 번만 0이면 되는 게 아니라, 이전 시작점의 dist가 남아 있으면 다음 BFS에서 방문한 칸으로 오판한다. 시작점마다 부르는 구조라 함수 첫 줄에 memset을 박았다.
- 섬이 여러 개인 지도면 어떤 시작점에서는 도달 못 하는 육지가 생기는데, 그 칸은 dist가 0으로 남아 최댓값 계산에 자연스럽게 안 잡힌다. 따로 처리할 게 없었다.
복잡도
- 시간: O((nm)²). 육지 칸 수만큼 BFS를 돌리고, BFS 한 번이 O(nm). 50×50 기준 최대 약 625만.
- 공간: O(nm). dist 배열과 큐.
2. 그림 (백준 1926) — flood fill, 리셋이 필요 없는 BFS
문제 재진술
0/1 도화지에서 1이 상하좌우로 붙어 있는 덩어리를 그림 하나로 친다. 그림이 몇 개인지, 제일 큰 그림이 몇 칸인지 출력한다.
접근을 잡기까지
“1로 연결된 것을 한 그림”, “대각선은 떨어진 것” — 문장 자체가 연결 요소(connected component) 정의라 접근은 바로 섰다. 고민한 건 알고리즘 선택이 아니라 DFS 재귀로 가도 되는가였다. 500×500이면 전부 1인 최악의 경우 재귀 깊이가 25만까지 갈 수 있다. 채점 환경 스택 사정에 따라 터질 수도 있는 깊이라, 재귀 대신 큐 기반 BFS로 갔다. 컴포넌트를 다 밟기만 하면 되는 문제라 DFS/BFS 어느 쪽이든 답은 같다.
거리가 필요 없고 개수만 세면 되니까 flood fill 패턴이다. “세는 문제는 칸마다 cnt++” 규칙 그대로, 대각선 제외 조건에 맞춰 4방향 dy/dx를 쓴다.
핵심 아이디어
도화지를 훑다가 안 밟은 1을 만나면 그림 하나 발견(cnt++), BFS로 그 덩어리를 전부 밟으면서 칸 수를 세고 최댓값을 갱신.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n, m, cnt, mx;
int a[504][504];
bool visited[504][504];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int bfs(int sy, int sx)
{
queue<pair<int, int>> q;
visited[sy][sx] = true;
q.push({ sy, sx });
int c = 0;
while (!q.empty()) {
int y = q.front().first, x = q.front().second;
q.pop();
c++;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (!a[ny][nx] || visited[ny][nx]) continue;
visited[ny][nx] = true;
q.push({ ny, nx });
}
}
return c;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j] && !visited[i][j]) {
cnt++;
mx = max(mx, bfs(i, j));
}
cout << cnt << endl << mx << endl;
return 0;
}
막힌 점·실수
- 그림이 하나도 없는 경우. 문제에 “그림이 없으면 넓이는 0”이라고 명시돼 있는데, 전역
cnt,mx가 0으로 시작하니 BFS가 한 번도 안 불리면 그대로0 0이 출력된다. 전역 0 초기화 덕에 공짜로 처리됐다. - visited 리셋이 필요 없는 경우 구분. 보물섬(2589)은 시작점마다 dist를 새로 재니까 매번 memset이 필수였는데, 이 문제는 컴포넌트끼리 겹치지 않아 visited를 한 번 칠한 건 영원히 유효하다. 전역 자동 0 한 번이면 끝. “BFS 여러 번 = 무조건 리셋”이 아니라, 같은 칸을 다시 계산해야 하는지가 기준이라는 걸 두 문제를 나란히 풀면서 정리했다.
- 입력이 보물섬과 달리
1 1 0 1 1처럼 공백 구분이라 string이 아니라 int 배열로 받았다. 붙어 나오면 string, 띄어 나오면 int — 입력 형태부터 확인하는 습관.
복잡도
- 시간: O(nm). 모든 칸은 정확히 한 번 방문된다(visited가 재방문을 막음). 500×500 = 25만.
- 공간: O(nm). a, visited 배열과 큐.
3. NBA 농구 (백준 2852) — 이벤트 시뮬레이션과 순서 함정
문제 재진술
48분 경기의 득점 로그(팀, MM:SS)를 보고, 각 팀이 스코어에서 앞서고 있던 시간의 총합을 MM:SS로 출력한다. 동점인 시간은 아무도 못 가져간다.
접근을 잡기까지
탐색도 자료구조도 아니고 순수 시뮬레이션이다. 무식한 방법부터 생각하면 경기 전체 2880초를 1초씩 돌면서 매 초마다 “지금 스코어가 몇 대 몇인지” 확인해 리드 팀에 1초씩 적립하는 것이다. 2880 × N(100) 수준이라 이것도 시간 안에 돌긴 한다. 그런데 골과 골 사이에는 스코어가 절대 안 변하니까 초 단위로 쪼갤 이유가 없다. 구간 단위로 몰아서 정산하는 게 맞다.
상태(스코어)가 이벤트(골) 시점에만 바뀌므로 이벤트 사이 구간을 통째로 처리하는 이벤트 시뮬레이션이다. MM:SS를 초로 통일해 정수 하나로 다루고, 출력할 때만 다시 MM:SS로 되돌린다.
핵심 아이디어
골이 들어올 때마다 “직전 골부터 지금까지” 구간을 그동안 이기고 있던 팀에 적립하고, 마지막 골 이후 48:00까지 남은 구간을 따로 정산한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n, s1, s2, t1, t2, pt;
int toSec(string s)
{
return ((s[0] - '0') * 10 + s[1] - '0') * 60 + (s[3] - '0') * 10 + s[4] - '0';
}
void print(int t)
{
cout << t / 60 / 10 << t / 60 % 10 << ':' << t % 60 / 10 << t % 60 % 10 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
while (n--) {
int a;
string s;
cin >> a >> s;
int t = toSec(s);
if (s1 > s2) t1 += t - pt;
if (s2 > s1) t2 += t - pt;
if (a == 1) s1++;
else s2++;
pt = t;
}
if (s1 > s2) t1 += 48 * 60 - pt;
if (s2 > s1) t2 += 48 * 60 - pt;
print(t1);
print(t2);
return 0;
}
막힌 점·실수
- 적립과 스코어 갱신의 순서. 이게 이 문제의 전부다. 구간 [직전 골, 이번 골]에서 이기고 있던 팀은 이번 골이 반영되기 전 스코어 기준이다. 스코어를 먼저 올리고 적립하면 이번 골이 과거 구간에 소급 적용돼 틀린다. “적립 먼저, 갱신 나중”을 루프 안에 고정.
- 경기 종료 정산 누락. 마지막 골 이후 48:00까지의 잔여 구간을 빼먹으면 예제 1부터 틀린다(20:00에 1골이면 남은 28분이 전부 1팀 리드고, 그게 답의 전부다). 루프가 끝난 뒤 같은 적립 로직을 한 번 더 돌렸다.
- 출력 자리수. 초를 MM:SS로 되돌릴 때 4:5를 04:05로 찍어야 한다. setw/setfill 대신
t/60/10, t/60%10식으로 자리별 숫자를 직접 출력해 패딩을 해결했다. - 시간 파싱은 형식이 MM:SS 고정(한 자리면 앞에 0)이라
s[0],s[1],s[3],s[4]고정 인덱스로 바로 계산했다. 예제 3(45:30 / 00:10)까지 세 예제 전부 손으로 따라가며 검증.
복잡도
- 시간: O(N). 골 하나당 상수 작업. N ≤ 100이라 사실상 즉시 끝난다.
- 공간: O(1). 스코어 2개, 적립 시간 2개, 직전 시각 하나.
두 BFS의 대비 정리
같은 격자 BFS인데 보물섬과 그림은 상태 관리가 정반대였다. 표로 묶으면 이렇게 갈린다.
| 항목 | 보물섬 (2589) | 그림 (1926) |
|---|---|---|
| 목적 | 최단거리의 최댓값 | 연결 요소 개수 + 최대 크기 |
| BFS 성격 | 다중 시작 (모든 육지가 시작점) | flood fill (안 밟은 1마다 1회) |
| 상태 배열 | dist (거리 저장) | visited (방문 여부) |
| 여러 번 호출 | 육지 칸마다 반복 | 컴포넌트마다 1회 |
| 매 호출 리셋 | 필수 (memset) — 같은 칸을 다음 시작점에서 다시 잼 | 불필요 — 컴포넌트끼리 안 겹침 |
| 방문 판정 | dist != 0 (+1 인코딩) | visited == true |
핵심은 “BFS를 여러 번 부르면 리셋한다”가 아니라 같은 칸을 다시 계산해야 하는가다. 보물섬은 시작점이 바뀔 때마다 모든 칸의 거리를 새로 재야 하니 리셋이 필수고, 그림은 한 번 어떤 그림에 속한 칸은 다른 그림에 다시 속할 일이 없으니 전역 visited 한 벌이면 끝난다.
오늘 배운 것 정리
- “최단거리들의 최댓값”은 시작점마다 BFS 한 번으로 충분하다 — 쌍마다 돌 필요 없이 한 BFS가 모든 칸까지의 최단거리를 준다. 가중치가 전부 1이면 다익스트라가 아니라 BFS.
- 거리 배열에서 미방문(0)과 거리(0)가 충돌하면 +1 인코딩으로 시작점을 1로 두고 반환 시 -1. 방문 판정이
dist != 0한 줄로 끝난다. - BFS 반복 호출 시 상태 리셋 여부의 기준은 “같은 칸을 다시 계산하는가” — 다중 시작(보물섬)은 매번 리셋, flood fill(그림)은 컴포넌트가 안 겹쳐 리셋 불필요.
- 이벤트 시뮬레이션은 구간 단위 정산 + 상태 갱신 순서가 전부 — “적립 먼저, 스코어 갱신 나중”, 그리고 마지막 이벤트 이후 종료 시각까지의 잔여 구간을 반드시 따로 정산.
- 입력 형태(붙어 있으면 string, 띄어 있으면 int)를 먼저 확인하는 습관 — 같은 격자 문제라도 파싱 방식이 갈린다.