문제 요약
문제 링크: 백준 17114 - 하이퍼 토마토
문제 설명
접근 방법
- 그래프 탐색의 대표 문제인 토마토와 비슷하다고 생각했다. 기본 토마토 문제는 2차원 배열과 3차원 배열을 전역에 선언하여 해결할 수 있는 문제인데, 이 문제에 그대로 적용하기엔 11차원의 배열의 크기를 정적으로 만들어서 사용할 수 없었다.
- 따라서 토마토 구조체를 만들어서 토마토가 어느 좌표에 있는지, 익은 지 얼마가 지났는지를 관리하는 큐를 활용한다.
- 토마토가 익는 것에 대한 전이 로직은 BFS로 처리하였다.
- 가장 어려운 것은 방문처리였다. map 혹은 set에 저장하기엔 시간복잡도에서 계속 걸렸다. map과 set의 탐색 시간 복잡도가 O(log N)인 것이 이유였다.
- 따라서 방문처리는 11차원 좌표를 1차원으로 평탄화 하여 고유 인덱스로 변환시킨 후, 방문처리를 O(1)에 효율적으로 처리할 수 있었다.
- 좌표 평탄화 기법은 각 좌표의 자리수에 다른 가중치를 부여하여 인덱스화 시킨다.
- 좌표 (3, 4) (x=3, y=4) 인덱스 = 4 * 10 + 3 = 43
- 좌표 (4, 3) (x=4, y=3) 인덱스 = 3 * 10 + 4 = 34
코드
- map과 set으로 인한 시간 초과 (61%) 코드 (로직은 맞는 듯 하다.)
#include <bits/stdc++.h>
using namespace std;
int m, n, o, p, q, r, s, t, u, v, w, sum, ans;
typedef struct tomato {
int cnt = 0;
int m, n, o, p, q, r, s, t, u, v, w;
}Tomato;
int d[22][11] = {
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1}
};
queue<Tomato>qe;
map<tuple<int, int, int, int, int, int, int, int, int, int, int>, bool > me;
void solve() {
while (qe.size()) {
Tomato cur = qe.front();
qe.pop();
ans = max(ans, cur.cnt);
for (int i = 0; i < 22; i++) {
Tomato nxt;
nxt.cnt = cur.cnt + 1;
nxt.m = cur.m + d[i][0];
nxt.n = cur.n + d[i][1];
nxt.o = cur.o + d[i][2];
nxt.p = cur.p + d[i][3];
nxt.q = cur.q + d[i][4];
nxt.r = cur.r + d[i][5];
nxt.s = cur.s + d[i][6];
nxt.t = cur.t + d[i][7];
nxt.u = cur.u + d[i][8];
nxt.v = cur.v + d[i][9];
nxt.w = cur.w + d[i][10];
if (nxt.m >= m || nxt.m < 0 ||
nxt.n >= n || nxt.n < 0 ||
nxt.o >= o || nxt.o < 0 ||
nxt.p >= p || nxt.p < 0 ||
nxt.q >= q || nxt.q < 0 ||
nxt.r >= r || nxt.r < 0 ||
nxt.s >= s || nxt.s < 0 ||
nxt.t >= t || nxt.t < 0 ||
nxt.u >= u || nxt.u < 0 ||
nxt.v >= v || nxt.v < 0 ||
nxt.w >= w || nxt.w < 0)
continue;
if (me[(make_tuple(nxt.m, nxt.n, nxt.o, nxt.p, nxt.q, nxt.r, nxt.s, nxt.t, nxt.u, nxt.v, nxt.w))])
continue;
sum--;
qe.push(nxt);
me[(make_tuple(nxt.m, nxt.n, nxt.o, nxt.p, nxt.q, nxt.r, nxt.s, nxt.t, nxt.u, nxt.v, nxt.w))] = 1;
}
}
if (sum == 0)
cout << ans;
else
cout << -1;
}
void input() {
cin >> m >> n >> o >> p >> q >> r >> s >> t >> u >> v >> w;
sum = m * n * o * p * q * r * s * t * u * v * w;
for (int i11 = 0; i11 < w; i11++)
for (int i10 = 0; i10 < v; i10++)
for (int i9 = 0; i9 < u; i9++)
for (int i8 = 0; i8 < t; i8++)
for (int i7 = 0; i7 < s; i7++)
for (int i6 = 0; i6 < r; i6++)
for (int i5 = 0; i5 < q; i5++)
for (int i4 = 0; i4 < p; i4++)
for (int i3 = 0; i3 < o; i3++)
for (int i2 = 0; i2 < n; i2++)
for (int i1 = 0; i1 < m; i1++) {
int a;
cin >> a;
Tomato tt;
tt.cnt = 0;
tt.m = i1;
tt.n = i2;
tt.o = i3;
tt.p = i4;
tt.q = i5;
tt.r = i6;
tt.s = i7;
tt.t = i8;
tt.u = i9;
tt.v = i10;
tt.w = i11;
if (a == 1) {
qe.push(tt);
sum--;
me[(make_tuple(tt.m, tt.n, tt.o, tt.p, tt.q, tt.r, tt.s, tt.t, tt.u, tt.v, tt.w))] = 1;
}
else if(a==-1) {
sum--;
me[(make_tuple(tt.m, tt.n, tt.o, tt.p, tt.q, tt.r, tt.s, tt.t, tt.u, tt.v, tt.w))] = 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
input();
solve();
}
- 토마토의 좌표를 평탄화(11차원 => 1차원)하여 방문처리한 정답 코드
#include <bits/stdc++.h>
using namespace std;
int m, n, o, p, q, r, s, t, u, v, w, sum, ans;
typedef struct tomato {
int cnt = 0;
int m, n, o, p, q, r, s, t, u, v, w;
}Tomato;
queue<Tomato>qe;
bool vis[1000001];
int d[22][11] = {
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1}
};
// 좌표 평탄화 (11차원 좌표를 1차원으로)
long long get_index(int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9, int c10, int c11) {
long long idx = c11;
idx = idx * v + c10;
idx = idx * u + c9;
idx = idx * t + c8;
idx = idx * s + c7;
idx = idx * r + c6;
idx = idx * q + c5;
idx = idx * p + c4;
idx = idx * o + c3;
idx = idx * n + c2;
idx = idx * m + c1;
return idx;
}
void solve() {
while (qe.size()) {
Tomato cur = qe.front();
qe.pop();
ans = max(ans, cur.cnt);
for (int i = 0; i < 22; i++) {
Tomato nxt;
nxt.cnt = cur.cnt + 1;
nxt.m = cur.m + d[i][0];
nxt.n = cur.n + d[i][1];
nxt.o = cur.o + d[i][2];
nxt.p = cur.p + d[i][3];
nxt.q = cur.q + d[i][4];
nxt.r = cur.r + d[i][5];
nxt.s = cur.s + d[i][6];
nxt.t = cur.t + d[i][7];
nxt.u = cur.u + d[i][8];
nxt.v = cur.v + d[i][9];
nxt.w = cur.w + d[i][10];
if (nxt.m >= m || nxt.m < 0 ||
nxt.n >= n || nxt.n < 0 ||
nxt.o >= o || nxt.o < 0 ||
nxt.p >= p || nxt.p < 0 ||
nxt.q >= q || nxt.q < 0 ||
nxt.r >= r || nxt.r < 0 ||
nxt.s >= s || nxt.s < 0 ||
nxt.t >= t || nxt.t < 0 ||
nxt.u >= u || nxt.u < 0 ||
nxt.v >= v || nxt.v < 0 ||
nxt.w >= w || nxt.w < 0)
continue;
if (vis[get_index(nxt.m, nxt.n, nxt.o, nxt.p, nxt.q, nxt.r, nxt.s, nxt.t, nxt.u, nxt.v, nxt.w)])
continue;
sum--;
qe.push(nxt);
vis[(get_index(nxt.m, nxt.n, nxt.o, nxt.p, nxt.q, nxt.r, nxt.s, nxt.t, nxt.u, nxt.v, nxt.w))] = 1;
}
}
if (sum == 0)
cout << ans;
else
cout << -1;
}
void input() {
cin >> m >> n >> o >> p >> q >> r >> s >> t >> u >> v >> w;
sum = m * n * o * p * q * r * s * t * u * v * w;
for (int i11 = 0; i11 < w; i11++)
for (int i10 = 0; i10 < v; i10++)
for (int i9 = 0; i9 < u; i9++)
for (int i8 = 0; i8 < t; i8++)
for (int i7 = 0; i7 < s; i7++)
for (int i6 = 0; i6 < r; i6++)
for (int i5 = 0; i5 < q; i5++)
for (int i4 = 0; i4 < p; i4++)
for (int i3 = 0; i3 < o; i3++)
for (int i2 = 0; i2 < n; i2++)
for (int i1 = 0; i1 < m; i1++) {
int a;
cin >> a;
Tomato tt;
tt.cnt = 0;
tt.m = i1;
tt.n = i2;
tt.o = i3;
tt.p = i4;
tt.q = i5;
tt.r = i6;
tt.s = i7;
tt.t = i8;
tt.u = i9;
tt.v = i10;
tt.w = i11;
if (a == 1) {
qe.push(tt);
sum--;
vis[(get_index(tt.m, tt.n, tt.o, tt.p, tt.q, tt.r, tt.s, tt.t, tt.u, tt.v, tt.w))] = 1;
}
else if(a==-1) {
sum--;
vis[(get_index(tt.m, tt.n, tt.o, tt.p, tt.q, tt.r, tt.s, tt.t, tt.u, tt.v, tt.w))] = 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
input();
solve();
}마무리
- 방문 처리에서 효율을 찾는 것이 어려웠던 문제
- n(n>1)차원 좌표에서 평탄화를 통해 인덱스화 할 수 있다.
'백준 문제풀이 > bfs' 카테고리의 다른 글
| [BOJ] 17472 다리 만들기 2 (0) | 2025.08.20 |
|---|---|
| [BOJ] 2251 물통 (0) | 2025.08.18 |
| [BOJ] 33851 DAG LCA (0) | 2025.06.22 |
| [BOJ] 17135 캐슬 디펜스 (0) | 2025.06.22 |
| [BOJ] 14948 군대 탈출하기 (0) | 2025.06.19 |