////////////////////dfs, bfs//////////////////////////////
/*
4503- dfs 방법
#include <stdio.h>
// 전역변수: 행렬, 이미 갔다왔는지 여부, 전체 노드 개수
int n;
int v[101]={};
int map[101][101]={};
void dfs(int node) {
v[node]=1;// 이미 간 길이다.
for(int i=1; i<=n; i++) {
if(map[node][i]==1&&v[i]==0) {dfs(i);}// 기준이된 node 옆 i와 연결되어 있고, 한번도 가보지 않은 길
}
}
int main()
{
int node, i, a, b, e, cnt=0;;
scanf("%d\n", &n);
scanf("%d\n", &e);
for(i=1; i<=e; i++) {
scanf("%d %d", &a, &b);
map[a][b]=map[b][a]=1;// 이차원 배열이므로 1-2 연결== 2-1eh 연결
}
dfs(1);
for(i=2; i<=n; i++) {// 1이 기준노드니까 자기 자신은 빼고 cnt하기
if(v[i]==1) {cnt++;}// 결국 v[i]가 1인 노드들 개수 세기
}
printf("%d", cnt);
}
*/
/*
4503-bfs
#include <stdio.h>
int n;
int v[101]={};
int map[101][101]={};
int queue[101];
int front=-1;
int rear=-1;
void enq(int node) {
queue[++rear]=node;
}
int deq() {
if(rear==front) return -1;
return queue[++front];
}
void bfs(int node) {
for(int i=1; i<=n; i++) {
if(map[node][i]==1&&v[i]==0) {enq(i); v[i]=1;}/// bfs에서 if(map[node][i]==1&&v[i]==0)이면 enq(i) 해주기
}
}
int main()
{
int node, i, a, b, e, j, cnt=0;
scanf("%d", &n);
scanf("%d", &e);
for(i=1; i<=e; i++) {
scanf("%d %d", &a, &b);
map[a][b]=map[b][a]=1;
}
v[1]=1;
bfs(1);
while(front!=rear)/// while(front!=rear) 다 빠질 때까지 deq하고 bfs 하기
{
j=deq();
bfs(j);
cnt++;
}
printf("%d", cnt);
}
*/
/*
/// bfs 할때마다 개수 세서 배열에 저장, 그리고 그 배열을 다시 오름차순 정렬
#include <stdio.h>
int a[26][26],n;
void dfs(int x, int y)
{
if(a[x][y]!=1||x<1||x>n||y<1||y>n) return; // 종료조건
a[x][y]=-1; //방문체크
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main() {
int i, j,cnt=0;
scanf("%d\n", &n);
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
scanf("%1d", &a[i][j]);
}
}
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
if(a[i][j]==1)
{
dfs(i,j);
cnt++;// 위에서 종료 안되고 주변에 1이 하나라도 있었을 시 단지 만들기는 성공한
}
}
}
}
*/
/*
4024
#include <stdio.h>
int w, h;
char a[101][101];
void dfs(int x, int y) {
if(a[x][y]!='L'||x<1||x>h||y<1||y>w) return;
a[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", &w, &h);
for(i=1; i<=h; i++) {
for(j=1; j<=w; j++) {
scanf(" %c", &a[i][j]); /// %c하기 전에 띄어쓰기 넣어야 정수와 문자 사이 입력된 엔터 지울 수 있음.
}
}
for(i=1; i<=h; i++) {
for(j=1; j<=w; j++) {
if(a[i][j]=='L') {
dfs(i, j);
cnt++;
}
}
}
printf("%d", cnt);
}
*/
/*
2605- 색깔=a[i][j] 정보도 필요
#include <stdio.h>
int a[8][8], r=0// 전역변수;
void dfs(int x, int y, int color)
{
if(a[x][y]!=color||x<1||x>7||y<1||y>7) return;// a[x][y]!=color, 즉 색깔이 다름.
a[x][y]=0;
r++;// 그러고 dfs들어갈 때마다 r++;(dfs를 3번 이상 해야 함)
dfs(x+1, y, color);
dfs(x-1, y, color);
dfs(x, y+1, color);
dfs(x, y-1, color);
}
int main()
{
int i, j, color, cnt=0;
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)// 0인 경우는 이미 탐색 끝남.
{
r=0;// dfs 들어가기 전에 a라는 변수를 0으로 초기화(다른 색깔 위해)
dfs(i, j, a[i][j]);// a[i][j]==color라는 것을 알려주기
if(r>=3){cnt++;}// 다시 메인함수 dfs 들어간 이후 a>=3이상인 경우에만 cnt++
}
}
}
printf("%d", cnt);
}
*/
/*
4572
#include <stdio.h>
int arr[101][101]={}, m, n,cnt=0; // 전역변수
int ca[600]={};// 넓이 저장
void dfs(int x, int y) {
if(arr[x][y]!=0||x<0||x>=m||y<0||y>=n) return;// 범위 조심.
arr[x][y]=-1;
ca[cnt]++;// dfs 할때마다 넓이 구하려고 +1씩.
dfs(x+1, y);
dfs(x-1, y);
dfs(x, y+1);
dfs(x, y-1);
}
int main() {
int i, j, k, a,b, c, d, q, p, temp;
int memo[101]={};
scanf("%d %d %d\n", &m, &n, &k);
for(i=1; i<=k; i++) { // 1인 부분 만들기
scanf("%d %d %d %d", &a, &b, &c, &d);
for(q=b; q<d; q++) { // 길이 반복 시 범위 조심.
for(p=a; p<c; p++) {
arr[q][p]=1;
}
}
}
for(i=0; i<m; i++) { // 0,0시작이니까 0부터 시작하고 i,j가 m이랑 n미만이어야 면적을 구할 수 있음.
for(j=0; j<n; j++) {
if(arr[i][j]==0) {
cnt++;// 위에 써야 ca[]배열이 1, 2, 3이 됨. 그래야 정렬(1부터 시작)할 때 안 헷갈림.
dfs(i, j);
}
}
}
printf("%d\n", cnt);
for(i=1; i<cnt; i++) {
for(j=1; j<=cnt-i; j++) {
if(ca[j]>ca[j+1]) {
temp=ca[j];
ca[j]=ca[j+1]; // 정렬.
ca[j+1]=temp;
}
}
}
for(i=1; i<=cnt; i++) {
printf("%d ", ca[i]);
}
}
4572 영역 구하기-색종이 1 참고
-해당하는 영역을 arr[i][j]=1; 로 생성// 원래는 다 0;
m=i, n=j// k가 1인부분. 그 분리된 영역의 개수를 찾는 것.
cnt 구하고,
분리된 영역의 넓이는 오름차순으로 정렬해서 빈칸 두고 출력
이때 i, j 범위 조심하기.
사각형 넓이는 배열값이 1인 것들 다 더해주면 나옴.
1지정하고서 main에서 dfs시행할 때 i랑 j 범위 달라.