글 읽기 - 틀렸습니다...[C++,BFS]

robin1001 7년 전 0

예제는 올바르게 작동합니다.

BFS의 몇 부분을 hard-coding 해 보았는데 BFS 탐색에는 문제가 없는것 같습니다.

메인 함수에서 배열을 저장하는 부분이나 다른 부분에서 문제가 생긴것 같은데 도통 모르겠습니다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int w,h;
int a[50][50];
int check[50][50];
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {-1,1,0,0,-1,1,-1,1};

void bfs(int x, int y){
	queue < pair<int, int> > q;
	q.push(make_pair(x,y));
	check[x][y] = 1;
	while(!q.empty()){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for(int i=0; i<8; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<h && ny>=0 && ny<w){
				if (a[nx][ny] == 1 && check[nx][ny] == 0) {
					q.push(make_pair(nx,ny));
					check[nx][ny] = 1;	
					//printf("%d %d, %d\n",nx,ny,a[nx][ny]);
				}
			}	
		}
	}
	return ;
}

int main(){
	int i,j;
	while(scanf("%d %d",&w,&h)){
		if(w==0 && h==0) break;
		for(i=0; i<51; i++){
			for(j=0; j<51; j++){
				check[i][j] = a[i][j] =0;
			}
		}
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				scanf("%d",&a[i][j]);
			}
		}
		int ans=0;
		for(i=0; i<h; i++){
			for(j=0; j<w; j++){
				if(a[i][j]==1 && check[i][j]==0){
					bfs(i,j);
					ans++;
					//printf("ans : %d\n",ans);
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

sgchoi5 7년 전 0

섬의 개수를 세는 것이라서.. BFS 를 안 쓰셔도 될듯한데...

크기가 작아서 완전 탐색으로 연결된 섬을 체크하시는 방식으로 하셔도 충분합니다..

sgchoi5 7년 전 0

a 와 check 의 크기는 50 인데 (index 범위 0~49), for 문에서는 0 ~ 50 까지 사용해서 초기화를 하시네요.

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

문제

문제

출처

ICPC

틀렸습니다...[C++,BFS]

robin1001 7년 전 0

sgchoi5 7년 전 0

sgchoi5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말