은수 IT 생존기

1697 - 숨바꼭질 https://www.acmicpc.net/problem/1697

문제 분류에서는 DFS라고 나와있는데, 사실상 알고보면 BFS 문제다.

아무 것도 모르던 나에게 DFS라고 하길래 노가다 하면서 계속 고민을 해봤는데 이거는 ㄹㅇ 암만 봐도 노답이었다. BFS 쓰자.

BFS를 잘 모르겠다면 체스 나이트 최단거리 구하는 문제부터 연습하자

9466 - 텀 프로젝트 https://www.acmicpc.net/problem/9466

기존의 흔히 사용하는 DFS는 2차원 배열에서 값을 찾는 것이지만,

해당 문제는 1차원 배열에서 문제를 찾는 방식임.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int map[100001];
int visit1[100001]; //map에서 한번이라도 체크되었는지 확인.
int visit2[100001]; //순회의 끝을 찾기 위함.

int total, visit_count=0;

void dfs(int i)
{
	int a;
	int next = map[i];
	visit1[i] = 1;

	//printf("visit1[%d] : %d,             visit_count: %d\n", i, map[i], visit_count);

	if(visit1[next] == 0)
	{
		dfs(next);
	}
	else
	{
		if(visit2[next] == 0)
		{
			for(a=next; a!=i; a=map[a])
			{
				visit_count++;
				//printf("i : %d, a: %d, map[%d] : %d, visit_count : %d\n", i, a, a, map[a], visit_count);
			}
			visit_count++;
		}
	}
	visit2[i] = 1;
}

int main(void)
{
	int i, total_count = 0, non_visit_count =0, n;

	scanf("%d", &total);
	fflush(stdin);


	while(total_count++ <total)
	{
		memset(map, 0, sizeof(map));
		memset(visit1, 0, sizeof(visit1));
		memset(visit2, 0, sizeof(visit2));

		scanf("%d", &n);
		for(i=1; i<=n; i++)
		{
			scanf("%d", &map[i]);
		}
		fflush(stdin);

		visit_count = 0;
		for(i=1; i<=n; i++)
		{
			if(visit1[i] == 0)
			{
				dfs(i);
			}
		}

		printf("%d\n", n-visit_count);
	}


	return 0;
}

2667-단지번호붙이기 acmicpc.net/problem/2667

해당 문제는 DFS 기초문제이다.

DFS를 사용한 이후에 나온 값들에 대한 정렬이 필요하다.

나는 처음에 퀵정렬 사용하려고 qsort함수를 사용하기 위해서 int compare(const void* a, const void* b) 함수를 새로 만들어서 사용하기도 했는데

왜인지 잘 모르겠지만 정렬이 잘 안됬음.

그래서 그냥 버블정령 만들어서 바로 사용했음.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int map[100][100];
int visit[100][100];
int* result;
int stack=0;
int n;
int max=0;

void dfs(int i, int j)
{
   int x, y,k;
   int dx[] = {0,1,0,-1};
   int dy[] = {1,0,-1,0};

   visit[i][j] = 1;
   
   max++;


   for(k=0; k<4; k++)
   {
      x=i+dx[k];
      y=j+dy[k];
      if(x<0 || y<0 || x>n-1 || y>n-1)
         continue;
      if(visit[x][y] == 0 && map[i][j] == map[x][y])
      {
         dfs(x, y);
      }
   }
}

int main(void)
{
   int i, j;
   char input[100];
   int temp;
   
   scanf("%d", &n);
   fflush(stdin);

   result = (int*)malloc(sizeof(int)*n*n);
   memset(map, 0, sizeof(map));
   memset(visit, 0, sizeof(visit));
   memset(result, 0, sizeof(result));

   for(i=0; i<n; i++)
   {
      scanf("%s", input);
      fflush(stdin);
      for(j=0; j<n; j++)
      {
         map[i][j] = input[j]-48;
      }
   }

   for(i=0; i<n; i++)
   {
      for(j=0; j<n; j++)
      {
         if(visit[i][j] == 0 && map[i][j] == 1)
         {
            max=0;
            dfs(i, j);   
            result[stack++] = max;
         }
      }
   }
   
   for(i=0; i<stack-1; i++)
   {
	   for(j=0; j<stack-1; j++)
	   {
		   if(result[j] > result[j+1])
		   {
			   temp = result[j];
			   result[j] = result[j+1];
			   result[j+1] = temp;
		   }
	   }
   }

   printf("%d\n", stack);
   for(i=0; i<stack; i++)
   {
      printf("%d\n", result[i]);
   }
   return 0;
}

10026-적록색약 acmicpc.net/problem/10026

DFS를 활용한 기초문제

dfs함수 안에서 조건문의 값 크기를 잘 설정하자.

저기서 x, y 조건을 약간 잘못걸어서 에러를 찾지 못하고 오래동안 헤맸음.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int arr[1000][1000];
int visit[1000][1000];
int result = 0;
int n = 0;

void dfs(int i, int j)
{
	int x,y,k;
	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};
	
	for(k=0; k<4; k++)
	{
		x = i + dx[k];
		y = j + dy[k];
		if( x<0 || y<0 || x>n-1 || y>n-1)
			continue;
		if(visit[x][y] == 0 && arr[i][j] == arr[x][y])
		{
			//printf("Log i,j,x,y : %d %d %d %d\n", i,j,x,y);
			//printf("Log 좌표값 : %d %d\n", arr[i][j], arr[x][y]);
			//printf("Log visit값 : %d %d\n\n\n", visit[i][j], visit[x][y]);
			visit[x][y] = 1;
			dfs(x,y);
		}
	}

}


int main(void)
{
	int i, j;
	char str[1000];


	memset(visit,0,sizeof(visit));
	memset(arr,0,sizeof(arr));


	scanf("%d", &n);
	fflush(stdin);
	for(i=0; i<n; i++)
	{
		scanf("%s", str);
		fflush(stdin);
		for(j=0; j<n; j++)
		{
			if(str[j] == 'R')
			{
				arr[i][j] = 2;
			}
			else if(str[j] == 'B')
			{
				arr[i][j] = 1;
			}
		}
	}
	

	//일반인
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			if(visit[i][j] == 0)
			{
				dfs(i, j);
				result ++;
			}
		}
	}
	
	printf("%d ", result);


	//장애인
	memset(visit,0,sizeof(visit));
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			if(arr[i][j] == 2)
			{
				arr[i][j] = 0;
			}
		}
	}
	result = 0;


	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			if(visit[i][j] == 0)
			{
				visit[i][j] = 1;
				dfs(i, j);
				result ++;
			}
		}
	}

	printf("%d\n", result);


	return 0;
}