/*
#include <stdio.h>
int off[101][101]= {};
int on[101][101]= {};
int a[101][101]= {};
int n,m;
void dfs(int x, int y, int c)
{
if(x>n||x<1||y>m||y<1)
return ;
if(c==1)
{
if(off[x][y]==0)
return ;
off[x][y]=0;
}
else
{
if(on[x][y]==1)
return ;
on[x][y]=1;
}
dfs(x+1,y,c);
dfs(x-1,y,c);
dfs(x,y+1,c);
dfs(x,y-1,c);
}
int main()
{
int t=0,i,j;
scanf("%d %d",&n,&m);
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
off[i][j]=a[i][j];
on[i][j]=a[i][j];
}
}
for(i=1; i<=n; i++) // 모두 1로 만들때 :
{
for(j=1; j<=m; j++)
{
if(on[i][j]==0)
{
dfs(i,j,0);
t++;
}
}
}
printf("%d ",t);
t=0;
for(i=1; i<=n; i++) // 모드 0으로 만들때 :
{
for(j=1; j<=m; j++)
{
if(off[i][j]==1)
{
dfs(i,j,1);
t++;
}
}
}
printf("%d",t);
return 0;
}
dfs
깊이 우선 탐색
스택 or 재귀
일단, 방문 할 수 있는 곳이 있으면 무조건 간다. 없으면 다시 돌아간다.
bfs
너비 우선 탐색
큐
방문 가능한 노드를 일단 다 탐색 -> 그 노드에서 방문 가능한 노드 탐색
*/
//큐 구현 + bfs
/*
#include <stdio.h>
int queue[5000];
int front=-1,rear=-1;
int a[101][101]= {};
int visited[101]= {};
int n,m,cnt=0;
//front : 데이터가 마지막으로 나간 위치
void enqueue(int data)
{
visited[data]=1;
queue[++rear]=data;
}
int dequeue()
{
if(front==rear)
return -1; //empty check
return queue[++front];
}
void view()
{
int i;
printf("queue>> ");
for(i=front+1; i<=rear; i++)
{
printf("%d ",queue[i]);
}
printf("\n");
}
int bfs(int node)
{
for(int i=1;i<=n;i++)
{
if(a[node][i]==1 && visited[i]!=1)
{
cnt++;
enqueue(i);
}
}
}
int main()
{
int i,j,c,d;
scanf("%d %d",&n,&m);
for(i=1; i<=m; i++)
{
scanf("%d %d",&c,&d);
a[c][d]=1;
a[d][c]=1;
}
bfs(1);
while(front!=rear)
{
bfs(dequeue());
}
printf("%d",cnt-1);
}
*/
/*
#include <stdio.h>
int front=-1,rear=-1,h,l;
int a[1001][1001];
int n,m;
int day=0;
typedef struct
{
int x,y;
} ar;
ar queue[1000001];
void enqueue(int x, int y)
{
if(x<1||x>n||y<1||y>m)
return ;
a[x][y]=1;
queue[++rear].x=x;
queue[rear].y=y;
}
ar dequeue()
{
return queue[++front];
}
void bfs(ar node)
{
if(a[node.x+1][node.y]==0)
{
enqueue(node.x+1,node.y);
}
if(a[node.x][node.y+1]==0)
{
enqueue(node.x,node.y+1);
}
if(a[node.x-1][node.y]==0)
{
enqueue(node.x-1,node.y);
}
if(a[node.x][node.y-1]==0)
{
enqueue(node.x,node.y-1);
}
}
int main()
{
int i,j;
scanf("%d %d",&m,&n);
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
{
enqueue(i,j);
}
}
}
while(front!=rear)
{
h = rear;
while(front<h)
{
bfs(dequeue());
}
day++;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
printf("\n");
}
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(a[i][j]==0)
{
printf("-1");
return 0;
}
}
}
printf("%d",day-1);
}
*/