코딩 이야기/백준 풀이
백준 7576번: 토마토 C++ 코드(BFS)
우기 woogi
2023. 3. 22. 08:57
반응형
//7576
#include<iostream>
#include<queue>
using namespace std;
int tomatoMap[1005][1005];
int m,n;
int cnt = 0;
struct xyLocation{
int y;
int x;
};
void bfs(int i[1000005], int j[1000005]){
queue <xyLocation> qq;
xyLocation temp;
for(int k=0; k<cnt; k++){
temp.y = i[k];
temp.x = j[k];
qq.push(temp);
}
while(!qq.empty()){
xyLocation now = qq.front();
qq.pop();
if(0<=now.y+1 && now.y+1 <n && tomatoMap[now.y+1][now.x] == 0){
temp.y = now.y+1;
temp.x = now.x;
tomatoMap[now.y+1][now.x] = tomatoMap[now.y][now.x] + 1;
qq.push(temp);
}if(0<=now.y-1 && now.y-1<n && tomatoMap[now.y-1][now.x] == 0){
temp.y = now.y-1;
temp.x = now.x;
tomatoMap[now.y-1][now.x] = tomatoMap[now.y][now.x] + 1;
qq.push(temp);
}if(0<=now.x+1 && now.x+1<m && tomatoMap[now.y][now.x+1] == 0){
temp.y = now.y;
temp.x = now.x+1;
tomatoMap[now.y][now.x+1] = tomatoMap[now.y][now.x] + 1;
qq.push(temp);
}if(0<=now.x-1 && now.x-1<m && tomatoMap[now.y][now.x-1] == 0){
temp.y = now.y;
temp.x = now.x-1;
tomatoMap[now.y][now.x-1] = tomatoMap[now.y][now.x] + 1;
qq.push(temp);
}
}
}
int main(){
cin >> m >> n;
int arry[1000005];
int arrx[1000005];
for(int i = 0; i<n; i++){
for(int j=0;j <m; j++){
cin >> tomatoMap[i][j];
}
}
for(int i = 0; i<n; i++){
for(int j=0;j <m; j++){
if(tomatoMap[i][j] == 1){
arry[cnt] = i;
arrx[cnt] = j;
cnt += 1;
}
}
}
bfs(arry, arrx);
int maxresult = 0;
int state = 0;
for(int i = 0; i<n; i++){
for(int j=0;j <m; j++){
if(tomatoMap[i][j] == 0){
state = 1;
}
if(maxresult < tomatoMap[i][j]){
maxresult = tomatoMap[i][j];
}
}
}
if(state == 0){
cout << maxresult-1;
}else{
cout << -1;
}
}
예전에 파이썬으로 풀었다가 재채점으로 틀려서 다시 c++으로 풀었다. 이 bfs 문제의 핵심은 토마토가 여러개있을때 각 토마토에서 동시에 bfs를 진행하는 것이다. 그래서 토마토 위치를 입력받고 토마토가 있는 곳을 아예 배열로 모았다가 한번에 bfs 큐에 넣어줌으로서 해결하였다.
반응형