[c++/알고리즘] 백준 7576 토마토 : BFS
- 문제 이해 :
1. 가중치가 모두 같은 경로를 탐색하며 , 최소 일수를 구하는 것이기 때문 -> BFS로 풀이한다.
2. 상자의 크기는 M*N // 문제를 똑바로 안읽고 의식의 흐름에 따라 N*M으로 입력받아서.. 시간이 걸렸다.
내가 작성한 코드
#include <iostream>
#include <queue>
using namespace std;
int map[1001][1001], ch[1001][1001];
int main(){
int n, m, a, ck=0, chz = 0 ,x, y, day=0;
// 앞, 뒤 , 오른, 왼 으로 이동하기 위한 배열
int dx[4] = {0 , 1, 0 ,-1};
int dy[4] = {1, 0, -1, 0};
queue<pair<int, int>> Q;
cin >> n >> m;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
cin >> a;
map[i][j] = a;
// 익은 토마토를 모두 queue에 넣는다.
if(a == 1) {
Q.push(make_pair(i, j));
ch[i][j] = 1;
}
// 이미 다 익었을 경우를 체크하기 위해 0이 하나라도 존재하는지 체크
if(a == 0){ chz = 1;}
}
}
// 0 이 존재 하지 않으면 다 익은 것으로 간주하고 0 출력
if(chz == 0){ cout << 0; return 0;}
while(!Q.empty()){
x = Q.front().first;
y = Q.front().second;
Q.pop();
for(int i=0; i<4; i++){
if(x+dx[i] < 0 || x+dx[i] >= m || y+dy[i]<0 || y+dy[i] >= n) continue;
// 토마토가 익지 않았으며, 이미 지나오지 않은 경우
if(ch[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 0){
Q.push(make_pair(x+dx[i], y+dy[i]));
// 인접한 익은 토마토의 일수 + 1
ch[x+dx[i]][y+dy[i]] = ch[x][y] + 1;
map[x+dx[i]][y+dy[i]] = 1;
}
}
}
// 여기까지 토마토가 익을 경우 최대 날짜.
// map 에 대해 포문돌면서 0 이 있으면(토마토 모두 다 익지 않은 경우) -1 출력
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(map[i][j] == 0 ){ cout << -1; return 0;}
}
}
// 그렇지 않으면 마지막으로 토마토가 익은 날짜에서 원래 익었던 토마토를 하루 센것을 제외해야 하므로 -1하여 출력
cout << ch[x][y] -1 << endl;
return 0;
}
Author And Source
이 문제에 관하여([c++/알고리즘] 백준 7576 토마토 : BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myeongs07/c알고리즘-백준-7576-토마토-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)