/*
#include <stdio.h>
typedef struct
{
char name[100];
int year;
int month;
int day;
} schedule;
int main()
{
int n,i,j;
schedule s[101],k;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%s %d %d %d",s[i].name,&s[i].year,&s[i].month,&s[i].day);
}
for(i=1; i<n; i++)
{
for(j=1; j<n-i+1; j++)
{
if(s[j].year>s[j+1].year)
{
k=s[j];
s[j]=s[j+1];
s[j+1]=k;
}
else if(s[j].year==s[j+1].year)
{
if(s[j].month>s[j+1].month)
{
k=s[j];
s[j]=s[j+1];
s[j+1]=k;
}
else if(s[j].month==s[j+1].month)
{
if(s[j].day>s[j+1].day)
{
k=s[j];
s[j]=s[j+1];
s[j+1]=k;
}
else if(s[j].day==s[j+1].day)
{
if(strcmp(s[j].name,s[j+1].name)>0)
{
k=s[j];
s[j]=s[j+1];
s[j+1]=k;
}
}
}
}
}
}
for(i=1; i<=n; i++)
{
printf("%s\n",s[i].name);
}
}
*/
/*
#include <stdio.h>
int partition(int a[],int begin, int end)
{
int n;
int pivot,L,R,k=0;
pivot=(begin+end)/2;
L=begin;
R=end;
while(L<R)
{
while(a[L]<a[pivot]&&L<R) L++;
while(a[R]>=a[pivot]&&L<R) R--;
if(L<R)
{
k=a[L];
a[L]=a[R];
a[R]=k;
if(L==pivot) pivot=R;
}
}
k=a[R];
a[R]=a[pivot];
a[pivot]=k;
return R;
}
int quicksort(int a[],int begin,int end)
{
int L,R,n;
L=begin;
R=end;
int part;
if(L<R)
{
part = partition(a,L,R);
quicksort(a,part+1,R);
quicksort(a,L,part-1);
}
}
int main()
{
int n,i,arr[101]={};
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
quicksort(arr,0,n-1);
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
}
#include <stdio.h>
// binary search
// arr[s] ~ arr[e] 에서 k값의 위치를 찾아서 리턴
int arr[101]={0,1,3,5,10};
int bs(int s, int e, int k)
{
int mid = (s+e)/2;
if(s>e) return -1;
if(arr[mid]==k) return mid;
else if(arr[mid]<k) bs(mid+1,e,k);
else bs(s,mid-1,k);
}
int main()
{
int n=4,i;
printf("%d",bs(1,n,3));
// for(int i=1;i<=n;i++)
// {
// printf("%d ",arr[i]);
// }
}
*/
/*#include <stdio.h>
int arr1[1000001]= {};
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr1[mid]==k) return mid;
else if(arr1[mid]<k) bs(mid+1,e,k);
else bs(s,mid-1,k);
}
int main()
{
int i,n,m,k;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&arr1[i]);
}
scanf("%d",&m);
for(i=1; i<=m; i++)
{
scanf("%d",&k);
printf("%d ",bs(1,n,k));
}
}*/
/*#include <stdio.h>
int arr[26][26]= {},n;
int danji[100]= {};
int cnt=0;
void dfs(int x, int y)// arr[x][y]에서 dfs
{
if(x<=0 || y<=0 || x>n||y>n||arr[x][y]!=1)
return ;
danji[cnt]++;
arr[x][y]=0;
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main()
{
int i,j,a[100]={};
scanf("%d",&n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%1d",&arr[i][j]);
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(arr[i][j]==1)
{
cnt++;
dfs(i,j);
}
}
}
printf("%d\n",cnt);
int k=0;
for(i=1;i<cnt;i++)
{
for(j=1;j<cnt-i+1;j++)
{
if(danji[j]>danji[j+1])
{
k=danji[j];
danji[j]=danji[j+1];
danji[j+1]=k;
}
}
}
for(i=1;i<=cnt;i++)
{
printf("%d\n",danji[i]);
}
}*/
/*
for(i=1; i<n; i++)
{
for(j=1;j<=n;j++)
a=a+danji[i];
}
printf("%d",a);
a=0;
for(i=1;i<=n;i++)
{
danji[i]=0;
}
#include <stdio.h>
char arr[101][101]={};
int w,h;
void dfs(int x, int y)
{
if(x<=0||y<=0||x>w||y>h||arr[x][y]!='L') return;
arr[x][y]='.';
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
dfs(x-1,y-1);
dfs(x-1,y+1);
dfs(x+1,y-1);
dfs(x+1,y+1);
}
int main()
{
int i,j,cnt=0;
scanf("%d%d",&h,&w);
for(i=1;i<=w;i++)
{
for(j=1;j<=h;j++)
{
scanf(" %c",&arr[i][j]);
}
}
for(i=1;i<=w;i++)
{
for(j=1;j<=h;j++)
{
if(arr[i][j]=='L')
{
cnt++;
dfs(i,j);
}
}
}
printf("%d",cnt);
}*/
/*
#include <stdio.h>
int a[8][8]= {};
int cmt=0,k=0;
void dfs(int x, int y,int color)
{
if(x<=0||y<=0||x>7||y>7||a[x][y]!=color) return;
k++;
a[x][y]=0;
dfs(x-1,y,color);
dfs(x,y-1,color);
dfs(x+1,y,color);
dfs(x,y+1,color);
}
int main()
{
int i,j;
for(i=1; i<=7; i++)
{
for(j=1; j<=7; j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1; i<=7; i++)
{
for(j=1; j<=7; j++)
{
if(a[i][j]!=0)
{
k=0;
dfs(i,j,a[i][j]);
if(k>=3) cmt++;
}
}
}
printf("%d",cmt);
}
#include <stdio.h>
int queue[10000]={};
int f=-1, r=-1;
//front : 마지막으로 나간 데이터의 "위치"
//rear : 마지막으로 들어온 데이터의 "위치"
void enq(int data)
{
rear++;
queue[rear]=data;
}
int deq()
{
front++;
return queue[front];
}
int main()
{
enq(10); //queue에 10 삽입
enq(20);
}
dfs bfs 참고
https://devuna.tistory.com/32
4421 bfs로 풀기
dfs : 4572 4697 4060
bfs : 4781
#include <stdio.h>
int queue[10000][2]={};
int front=-1, rear=-1
void bfs(int x, int y)
{
int a, b;
enq(x,y);
while(front!=rear)//큐가 비어있지않는동안
{
front++;
a = queue[front][0];
b = queue[front][1];
if(a-1>0 && arr[a-1][b]==1) enq(a-1,b);
if()
if()
if()
}
}
void enq(int dx,int dy)
{
rear++;
arr[dx][dy]=0; //방문 체크
queue[rear][0]=dx;
queue[rear][1]=dy;
}
int main()
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%1d",&arr[i][j]);
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(arr[i][j]==1)
{
cnt++;
bfs(i,j);
}
}
}
}
*/