/*
#include <stdio.h>
int n,i,j,arr[120][120]={},a[120][120]={},max=0,sum=0,cnt;
void dfs()
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if (a[i][j]>cnt)
{
f(i,j);
sum++;
}
}
}
if (sum>max)
{
max=sum;
}
}
void f(int y,int x)
{
a[y][x]=0;
if(a[y+1][x]>cnt)
{
f(y+1,x);
}
if(a[y-1][x]>cnt)
{
f(y-1,x);
}
if(a[y][x+1]>cnt)
{
f(y,x+1);
}
if(a[y][x-1]>cnt)
{
f(y,x-1);
}
}
int main()
{
int maxx=0;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d", &arr[i][j]);
a[i][j]=arr[i][j];
if (arr[i][j]>maxx)
{
maxx = arr[i][j];
}
}
}
for(cnt=0;cnt<=maxx;cnt++)
{
sum=0;
dfs();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
a[i][j] = arr[i][j];
}
}
}
printf("%d", max);
return 0;
}
*/
/*
#include <stdio.h>
int i,j,sum=0,arr[30][30]={},l=0,p=-10,a=1;
void dfs(int y, int x)
{
l = arr[y][x];
if (arr[y+1][x]==l)
{
if(arr[y-1][x]!=l)
{
a=1;
f(y,x,2,1);
if(p==-1000)
{
p=-10;
}
}
}
if (arr[y][x+1]==l)
{
if(arr[y][x-1]!=l)
{
a=1;
f(y,x,3,1);
if(p==-1000)
{
p=-10;
}
}
}
if (arr[y+1][x+1]==l)
{
if(arr[y-1][x-1]!=l)
{
a=1;
f(y,x,5,1);
if(p==-1000)
{
p=-10;
}
}
}
if (arr[y-1][x+1]==l)
{
if(arr[y+1][x-1]!=l)
{
a=1;
f(y,x,7,1);
if(p==-1000)
{
p=-10;
}
}
}
}
void f(int y, int x, int n, int o)
{
if (p==-1000)
{
return;
}
if (n==2)
{
if (arr[y+1][x]==l)
{
a++;
f(y+1,x,n,o+1);
}
}
if (n==3)
{
if (arr[y][x+1]==l)
{
a++;
f(y,x+1,n,o+1);
}
}
if (n==5)
{
if (arr[y+1][x+1]==l)
{
a++;
f(y+1,x+1,n,o+1);
}
}
if (n==7)
{
if (arr[y-1][x+1]==l)
{
a++;
f(y-1,x+1,n,o+1);
}
}
if (a==5 && o==1)
{
p=100;
printf("%d\n%d %d\n", arr[i][j],i,j);
}
else if (a>5)
{
p=-1000;
}
}
int main()
{
for (i=1;i<=19;i++)
{
for (j=1;j<=19;j++)
{
scanf("%d", &arr[i][j]);
}
}
for (i=1;i<=19;i++)
{
for (j=1;j<=19;j++)
{
if (arr[i][j] != 0)
{
dfs(i,j);
if (p==100)
{
return 0;
}
}
}
}
printf("0");
return 0;
}
*/
/*
#include <stdio.h>
int i,j,arr[10][10]={},k,l,sum=0;
void dfs(int y,int x)
{
if (arr[y][x]!=l)
{
return;
}
k++;
arr[y][x]=0;
dfs(y+1,x);
dfs(y-1,x);
dfs(y,x-1);
dfs(y,x+1);
}
int main()
{
for(i=1;i<=7;i++)
{
for(j=1;j<=7;j++)
{
scanf("%d", &arr[i][j]);
}
}
for(i=1;i<=7;i++)
{
for(j=1;j<=7;j++)
{
if(arr[i][j]!=0)
{
k=0;
l=arr[i][j];
dfs(i,j);
if (k>=3)
{
sum++;
}
}
}
}
printf("%d", sum);
return 0;
}
수3
목6 ~
토1 (ok)
dfs : 스택 or 재귀
bfs : 큐
이 노드에서 갈 수 있는 노드를 전부 "방문" : dfs , bfs
이 노드에서 7번 노드까지의 최단 "경로" : dfs (stack, 코드간단)
이 노드에서 7번 노드까지의 최단 "거리" : bfs (큐, 코드 복잡)
1.단지번호 bfs로 풀면서 연습하기
2. 1512 -> 3122 -> 4781 -> 4039 ( bfs로 풀수 있는 문제 )
*/