글 읽기 - 맞긴했는데 궁금한것이 있어서 글을 남깁니다

johyesong8686 4년 전 0

다른분들은 dfs bfs로 푸셨다는데 잘 모르겠어서 이런 식으로 풀어서 맞았습니다.

이 코드는 bfs가 아닌거죠 ?

그리고

bfs와 활용하셔서 푸신 분들은 어떻게

논리는 세워서 접근하셨는지 궁금합니다. ㅜㅜ

제가 어려웠던 부분은 1이 여러 부분에 있을 시에 동시에 반영되게 하는 논리를 어떻게 해야할 지 었거든요

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int check[1000][1000];
int b[1000][1000];
int M,N;
int cnt;

vector<pair<int,int> > v;
vector<pair<int,int> > v2;
void find(int i,int j){
	
	if(check[i][j]==1){
		return;
	}
	if(b[i][j]==-1){
		return;
	}	
	check[i][j]=1;
	if(i-1>=0&&b[i-1][j]==0){
	b[i-1][j]=1;
	v2.push_back(make_pair(i-1,j));
	}
	if(i+1<N&&b[i+1][j]==0){
	b[i+1][j]=1;
	v2.push_back(make_pair(i+1,j));
		
	}	
	if(j-1>=0&&b[i][j-1]==0){
	b[i][j-1]=1;
	v2.push_back(make_pair(i,j-1));	
	}
	if(j+1<M&&b[i][j+1]==0){
	b[i][j+1]=1;
	v2.push_back(make_pair(i,j+1));		
	}
	
	
}
bool full(){
	for(int i=0; i<N;i++){
		for(int j=0; j<M;j++){
		
		if(b[i][j]==0){
			return false;
		}	
		}
	
	}
	return true;	
	
	
}
int main(void){
	
	cin >> M >>N;
	
	for(int i=0; i<N;i++){
		for(int j=0; j<M;j++){
		cin >>b[i][j];
		if(b[i][j]==1){
			v.push_back(make_pair(i,j));
		}	
		}
	
	}
	while(!v.empty()){
	cnt++;
	//printf("vsize %d ,\n",v.size());
	for(int i=0; i<v.size();i++){
		int x=v[i].first;
		int y=v[i].second;
		find(x,y);			
	}
	v.clear();
	v.assign(v2.begin(),v2.end());
	v2.clear();	
	}
	
	
	if(full()){
		cout <<cnt-1;
	}else{
		cout <<-1;
	}
	
	



	return 0;
}

shg9411 4년 전 0

bfs가 맞지않나요?

저 또한 큐에 담고 그 사이즈만큼 for문을 돌리고

늘어난 것들을 큐에 담고 그 사이즈만큼 for문을 돌리고

같은 방식으로 풀었습니다.

johyesong8686 4년 전 0

shg9411

ㅇ ㅏ 생각해보니 그렇네요! 저도 모르게 bfs로 풀었네욬ㅋㅋㅋ

queue사용 해도 편할텐데 제가 그걸 생각을 못햇네요 ㅜㅜㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맞긴했는데 궁금한것이 있어서 글을 남깁니다

johyesong8686 4년 전 0

shg9411 4년 전 0

johyesong8686 4년 전 0

shg9411

ㅇ ㅏ 생각해보니 그렇네요! 저도 모르게 bfs로 풀었네욬ㅋㅋㅋ

queue사용 해도 편할텐데 제가 그걸 생각을 못햇네요 ㅜㅜㅎㅎ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말