#include<stdio.h>
int arr[60][60]={0,};
int visited[60][60]={0,};
void dfs(int i,int k){
visited[i][k]=1;
if(arr[i][k-1]==1&&visited[i][k-1]==0)
dfs(i,k-1);
if(arr[i][k+1]==1&&visited[i][k+1]==0)
dfs(i,k+1);
if(arr[i-1][k]==1&&visited[i-1][k]==0)
dfs(i-1,k);
if(arr[i+1][k]==1&&visited[i+1][k]==0)
dfs(i+1,k);
if(arr[i-1][k-1]==1&&visited[i-1][k-1]==0)
dfs(i-1,k-1);
if(arr[i-1][k+1]==1&&visited[i-1][k+1]==0)
dfs(i-1,k+1);
if(arr[i+1][k+1]==1&&visited[i+1][k+1]==0)
dfs(i+1,k+1);
if(arr[i+1][k-1]==1&&visited[i+1][k-1]==0)
dfs(i+1,k-1);
}
int main(void){
int w,h;
while(1){
int count;
scanf("%d %d",&w,&h);
for(int i=1;i<=h;i++){
for(int k=1;k<=w;k++)
scanf("%d",&arr[i][k]);
}
if(w==0&&h==0)
break;
count=0;
for(int i=1;i<=h;i++){
for(int k=1;k<=w;k++){
if(arr[i][k]==1&&visited[i][k]==0){
count++;
dfs(i,k);
}
}
}
printf("%d\n",count);
for(int i=1;i<=h;i++){
for(int k=1;k<=w;k++){
arr[i][k]=0;
visited[i][k]=0;
}
}
}
return 0;
}
개선된 코드
#include<stdio.h>
#include<string.h>
int arr[60][60]={0,};
int visited[60][60]={0,};
int dw[10]={0,0,1,1,1,-1,-1,-1};
int dh[10]={1,-1,0,1,-1,0,1,-1};
void dfs(int i,int k){
int w,h;
visited[i][k]=1;
for(int t=0;t<8;t++){
w=k+dw[t];
h=i+dh[t];
if(arr[h][w]==1&&visited[h][w]==0)
dfs(h,w);
}
}
int main(void){
int w,h;
int count;
while(1){
scanf("%d %d",&w,&h);
for(int i=1;i<=h;i++){
for(int k=1;k<=w;k++)
scanf("%d",&arr[i][k]);
}
if(w==0&&h==0)
break;
count=0;
for(int i=1;i<=h;i++){
for(int k=1;k<=w;k++){
if(arr[i][k]==1&&visited[i][k]==0){
count++;
dfs(i,k);
}
}
}
printf("%d\n",count);
for(int i=1;i<=h;i++){
memset(arr[i],0,sizeof(int)*60);
memset(visited[i],0,sizeof(int)*60);
}
}
return 0;
}
반복되는 코드 없이 깔끔한 코드 짜기
배열 초기화할 때 memset사용
이중배열에 memset사용하는 방법
[C언어/DP] 10844 : 쉬운 계단 수 (0) | 2022.01.09 |
---|---|
1157 : 단어 공부 (0) | 2022.01.06 |
[C언어/DFS] 2667 : 단지번호붙이기 (0) | 2022.01.04 |
2606 : 바이러스 (0) | 2022.01.04 |
1065 : 한수 (0) | 2022.01.03 |