4963번 - 섬의 개수
BFS로 풀었고, 왠지 막연한 질문일 수도 있는데,..
진짜.. 대체 어디서 틀렸는지 모르겠습니다 ㅠㅠ..
혹시 반례나 코드 중 문제있는 부분 아시는 분 도와주시기 바랍니다 ㅠㅠㅠ
#include<stdio.h>int map[55][55];int w,h,gesu;void BFS(int a, int b);int main(void){ for(;;) { gesu=0; scanf("%d %d",&w,&h); if(w==0||h==0) break;
for(int i=1;i<=w;i++) for(int j=1;j<=h;j++) scanf("%d",&map[i][j]);
for(int i=1;i<=w;i++) for(int j=1;j<=h;j++) if(map[i][j]==1) { gesu++; BFS(i,j); } printf("%d\n",gesu); }}void BFS(int a, int b){ map[a][b]=0; if(map[a-1][b-1]==1) BFS(a-1,b-1); if(map[a-1][b]==1) BFS(a-1,b); if(map[a-1][b+1]==1) BFS(a-1,b+1); if(map[a][b-1]==1) BFS(a,b-1); if(map[a][b+1]==1) BFS(a,b+1); if(map[a+1][b-1]==1) BFS(a+1,b-1); if(map[a+1][b]==1) BFS(a+1,b); if(map[a+1][b+1]==1) BFS(a+1,b+1);}
1.일단은 예제 통과가 안되구용
2. w,h를 바꿔보세요. 잘못넣으셨네용 그거 바꾸니까 맞게 나오네요.
3. 구현하신 부분은 BFS가 아니라 DFS구용
4. 함수부분 내용을 밑에 코드처럼 하면 더 깔끔하게 나와용
댓글을 작성하려면 로그인해야 합니다.
vc0612 6년 전
BFS로 풀었고, 왠지 막연한 질문일 수도 있는데,..
진짜.. 대체 어디서 틀렸는지 모르겠습니다 ㅠㅠ..
혹시 반례나 코드 중 문제있는 부분 아시는 분 도와주시기 바랍니다 ㅠㅠㅠ
#include<stdio.h>
int map[55][55];
int w,h,gesu;
void BFS(int a, int b);
int main(void)
{
for(;;)
{
gesu=0;
scanf("%d %d",&w,&h);
if(w==0||h==0) break;
for(int i=1;i<=w;i++)
for(int j=1;j<=h;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=w;i++)
for(int j=1;j<=h;j++)
if(map[i][j]==1)
{
gesu++;
BFS(i,j);
}
printf("%d\n",gesu);
}
}
void BFS(int a, int b)
{
map[a][b]=0;
if(map[a-1][b-1]==1) BFS(a-1,b-1);
if(map[a-1][b]==1) BFS(a-1,b);
if(map[a-1][b+1]==1) BFS(a-1,b+1);
if(map[a][b-1]==1) BFS(a,b-1);
if(map[a][b+1]==1) BFS(a,b+1);
if(map[a+1][b-1]==1) BFS(a+1,b-1);
if(map[a+1][b]==1) BFS(a+1,b);
if(map[a+1][b+1]==1) BFS(a+1,b+1);
}