오늘은 백준 7576번 문제, 토마토를 가져왔습니다
문제 내용은 파악했다고 가정하고 제 사고의 흐름을 바로 설명해볼게요
토마토가 1개라고 가정해볼까요 ?
이 문제는 한 점에서 퍼져나가 모든 토마토을 방문하게 하는 데 ‘최소’ 몇일이 지나야하는지 묻고 있습니다
‘그래프의 최단거리’ 문제와 상당히 유사해보입니다
'그래프 최단거리'라는 어구가 입력 x로 주어지면 저는 반사적으로 'BFS'라는 출력 y를 떠올리는데요
구종만선생님의 책 알고리즘 문제해결전략에서는 DFS와 달리 BFS는 그래프 상에서 ‘최단거리’를 찾는 용도로 제한된다고 했었습니다 이에 반해서 DFS는 그래프의 고유 특징을 추출하는 데 유용해 사용 범위가 넓다고 했죠
아래 코드는 BFS 기본 골격입니다 (예제 소스코드는 c++로 작성되었습니다)
void bfs(int start, const vector<vector<int>>& graph, vector<bool>& visited) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
cout << curr << " "; // 방문한 노드 출력
for (int next : graph[curr]) {
if (!visited[next]) {
q.push(next);
visited[next] = true;
}
}
}
}
위 코드는 2차원 매트릭스 graph로 인접리스트를 구현하고 있습니다
bfs 구현의 핵심은 자료구조 queue로, 큐를 통해 먼저 투입된 노드를 먼저 방문하고, 이로써 깊이가 얕은 노드들부터 방문할 수 있게 됩니다
또 노드 방문여부를 나타내는 벡터 visited를 통해 노드를 중복해서 방문하지 않게 하고, while 무한루프를 벗어날 수 있게 해줍니다
매 턴마다 큐에서 노드를 꺼내 해당 노드의 인접노드를 큐에 모두 넣은 다음, 인접노드들은 방문한 상태로 처리해주고 있습니다 매 턴마다 방문한 노드는 pop() 해주는 걸 잊지 마세요! (잊으면 무한루프에 빠지게 됩니다…)
토마토 문제의 큰 틀은 우선 이 BFS 소스코드인데, 변수가 있습니다
초기 단계에 익은 토마토가 2개라면 큐에 두 토마토로 인해 익은 토마토들이 들어가야 합니다 그런데 기존 bfs와 달리 같은 날에 익은 토마토(노드)들은 한번에 pop() 해야합니다 문제에서 요구하는 건 모든 토마토가 다 익는데 걸리는 ‘시간’이기 때문이죠 (다른 말로, 시간의 흐름에 따라 익은 토마토들을 구분할 수 있어야 합니다)
제가 생각해낸 방법은 bfs의 큰 틀은 유지하되 2개의 큐를 운용하는 것이었습니다
다음 코드는 응용된 bfs의 큰 틀입니다
while(!q1.empty()) {
while (!q1.empty()) {
int curr = q1.front();
q1.pop();
for (int next : graph[curr]) {
if (!visited[next]) {
q2.push(next);
visited[next] = true;
}
}
}
while (!q2.empty()) {
int curr = q2.front();
q2.pop();
for (int next : graph[curr]) {
if (!visited[next]) {
q1.push(next);
visited[next] = true;
}
}
}
}
두 개의 큐는 다음과 같이 운용됩니다
타임라인 상 임의의 시점 t에 대해 현재 시점 t에 방문할 노드는 q1에서 꺼내지고, 다음에 방문해야 할 노드(즉 t+1에 방문될 노드이자 q1에서 꺼내진 노드와 인접한 노드들)들은 q2에 추가됩니다
이 매커니즘은 홀수 시점에 방문할 노드와 짝수 시점에 방문할 노드를 정확히 구분합니다
두 큐를 순회하는 두 while문을 큰 while문이 감싸고 있습니다 이 반복문은 두 큐가 빈 상태인지 확인하는, 즉 탐색이 끝났는지 판단하는 기존 bfs 코드의 while문과 같은 역할을 합니다
이제 while문 사이사이에 시간 t를 업데이트 해주고(t++) 다음과 같은 조건들을 추가해주면 됩니다
마지막으로 체스판과 같이 특수한 형태로 그래프를 표현하는 코드입니다
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
// 가로 M, 세로 N 크기의 매트릭스를 탐색
int nextn, nextm;
for(int i=0;i<4;++i) {
nextn=nindex+dx[i];
nextm=mindex+dy[i];
if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
if(box[nextn][nextm]==0) { q2.push({nextn, nextm}); }
}
체스판, 바둑판은 흔히 2차원 좌표로 나타낼 수 있는데요 말의 이동에 제약이 있다면 (예. 상하좌우로만 이동가능, 대각선 이동불가) 좌표 상에서 증분을 뜻하는 dx,dy 변수를 이용해 보다 쉽게 탐색을 구현할 수 있습니다
이때 취할 수 있는 선택지는 4가지이므로 dx, dy 역시 크기 4의 배열로 표현할 수 있습니다
2차원 벡터로 그래프를 표현하면 인접리스트 또는 인접행렬이 불필요하다는 장점이 있습니다
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int main() {
fastio;
queue<pair<int,int>> q1,q2;
int days=0;
int rotton=0, non=0;
int N,M;
cin >> M >> N;
int numBox=M*N;
vector<vector<int>> box(N,vector<int>(M,-1));
for(int n=0;n<N;++n) {
for(int m=0;m<M;++m) {
cin >> box[n][m];
if(box[n][m]==1) { rotton++; q1.push({n,m}); }
if(box[n][m]==-1) non++;
}
}
if(rotton+non==numBox) { cout << 0 << '\n'; return 0; }
while(!q1.empty()) {
while(!q1.empty()) {
int nindex=q1.front().first; int mindex=q1.front().second; q1.pop();
int nextn, nextm;
for(int i=0;i<4;++i) {
nextn=nindex+dx[i];
nextm=mindex+dy[i];
if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
if(box[nextn][nextm]==0) { box[nextn][nextm]=1; q2.push({nextn, nextm}); rotton++; }
}
if(rotton+non==numBox) { cout << days+1 << '\n'; return 0; }
}
days++;
if(q2.empty()) break;
while(!q2.empty()) {
int nindex=q2.front().first; int mindex=q2.front().second; q2.pop();
int nextn, nextm;
for(int i=0;i<4;++i) {
nextn=nindex+dx[i];
nextm=mindex+dy[i];
if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
if(box[nextn][nextm]==0) { box[nextn][nextm]=1; q1.push({nextn, nextm}); rotton++; }
}
if(rotton+non==numBox) { cout << days+1 << '\n'; return 0; }
}
days++;
}
if(rotton+non != numBox) { cout << -1 << '\n'; return 0; }
cout << days << '\n';
return 0;
}