[코딩테스트 C++] 토마토
오늘의 문제
https://www.acmicpc.net/problem/7576
토마토
참고한 풀이
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 1000;
vector<vector<int>> box(MAX, vector<int>(MAX, 0));
bool visit[MAX][MAX] = {false, };
int n, m;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
queue<pair<pair<int, int>, int>> q;
int cnt;
// 토마토
void solution(){
while(!q.empty()){
int row = q.front().first.first;
int col = q.front().first.second;
cnt = q.front().second;
q.pop();
for(int i=0;i<4;i++){
int R = row + di[i];
int C = col + dj[i];
if(R>=n || R<0 || C>=m || C<0)
continue;
if(visit[R][C] == false && box[R][C] == 0){
visit[R][C] = true;
q.push(make_pair(make_pair(R, C), cnt +1));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>m >>n;
vector<vector<int>> pair;
for(int j=0;j<n;j++){
for(int i = 0;i<m;i++){
cin>>box[j][i];
if(box[j][i] == 1){
q.push(make_pair(make_pair(j, i), 0));
visit[j][i] = true;
}
}
}
solution();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visit[i][j] && box[i][j] == 0){
cout<<-1<<endl;
return 0;
}
}
}
cout<<cnt<<endl;
return 0;
}
배울 점
- BFS활용법을 또 하나 배웠다. 시작되어야하는 점을 알고 있으면, 모든 지점에서부터의 가장 짧은 depth를 알 수 있다.
- 그래프문제를 풀 때 아주 잘 쓸 수 있을것 같다.
Author And Source
이 문제에 관하여([코딩테스트 C++] 토마토), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@huijae0817/코딩테스트-C-토마토저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)