따라서, 기존의 구현 코드에서 상자를 3차원 배열로 변경하고 Z 좌표가 바뀌는 경우를 추가해주었다.
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct boxPos {
int z, y, x;
};
int M, N, H;
int box[101][101][101];
queue<boxPos> ripeTomatoPosQ;
int dz[6] = { 0,0,0,0,1,-1 };
int dy[6] = { 0,0,1,-1,0,0 };
int dx[6] = { 1,-1,0,0,0,0 };
int getDay(int unripeTomato) {
int day = 0;
while (unripeTomato > 0) {
day++;
int newRipeTomatoCnt = ripeTomatoPosQ.size();
// 안익은 토마토가 남아있는 상태에서 새롭게 익은 토마토가 없다면 토마토를 모두 익히는건 불가능하다.
if (newRipeTomatoCnt == 0)
return -1;
for (int i = 0; i < newRipeTomatoCnt; i++) {
int hereZ = ripeTomatoPosQ.front().z;
int hereY = ripeTomatoPosQ.front().y;
int hereX = ripeTomatoPosQ.front().x;
ripeTomatoPosQ.pop();
// 주변의 토마토를 익힌다.
for (int i = 0; i < 6; i++) {
int nearZ = hereZ + dz[i];
int nearY = hereY + dy[i];
int nearX = hereX + dx[i];
if (nearZ >= 0 && nearZ < H && nearY >= 0 && nearY < N && nearX >= 0 && nearX < M)
if (box[nearZ][nearY][nearX] == 0) {
// 안익은 토마토를 익은 토마토로 바꾸고 안익은 토마토의 갯수를 1 감소시킨다.
box[nearZ][nearY][nearX] = 1;
unripeTomato--;
// 새롭게 익은 토마토의 좌표를 큐에 담는다.
ripeTomatoPosQ.push({ nearZ, nearY, nearX });
}
}
}
}
return day;
}
int main(void) {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> M >> N >> H;
int unripeTomato = 0;
for (int z = 0; z < H; z++) {
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
int state;
cin >> state;
box[z][y][x] = state;
if (state == 0)
unripeTomato++;
else if (state == 1)
ripeTomatoPosQ.push({ z,y,x });
}
}
}
cout << getDay(unripeTomato) << endl;
return 0;
}
그래프의 모든 정점을 방문할 때 까지 bfs나 dfs를 수행한 다음, 수행한 횟수가 곧 연결 요소의 갯수가 된다.
정점의 개수가 많고 양방향 그래프로 표현해야 하기 때문에 인접 행렬보단 인접 리스트로 그래프를 구현하는 것이 효율적이고 직관적이라고 생각한다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
vector<int> adj[1001];
bool visited[1001];
void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int here = q.front();
q.pop();
for (int i = 0; i < adj[here].size(); i++) {
int next = adj[here][i];
if (!visited[next]) {
q.push(next);
visited[next] = true;
}
}
}
}
int getConnectedComponent() {
int result = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
result++;
bfs(i);
}
}
return result;
}
int main(void) {
cin >> N >> M;
// 양방향 그래프로 구현할 것
while(M--) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cout << getConnectedComponent() << endl;
return 0;
}