알고리즘 백준 2667 단지번호 붙이기 해설

일단, 

 

이 문제를 풀려면 DFS 깊이 탐색 알고리즘 방식을 알아야된다.

그리고 재귀 함수라는 것에 대한 이해

그리고 2차원 배열이라는 의미를 알고,

정렬까지 들어가야한다~ 오름차순으로

 

#include<stdio.h>

//2667번 https://www.acmicpc.net/problem/2667
//깊이확인
/*
7
0110100
0010101
1110101
0000111
0100000
0111110
0111000
*/
void dfs(int nowrow, int nowcol, int dange, int n);
int xasis[4] = { -1, 0, 1, 0 }, yasis[4] = { 0, 1, 0, -1 };



int visited[25][25] = { 0, };
int map[25][25];
int dange_map[1000] = { 0, };
int dange = 0;
int main() {
	int n = 0; //지도의크기
	
	scanf("%d", &n);


	//초기 행열 입력 받기, visited 초기화
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			scanf("%1d", &(map[x][y]));
		}
		
	}


	//첫 노드 찾기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && visited[i][j] == 0) {	
				
				dfs(i, j, dange, n);
				dange = dange + 1;
				

			}
			else{
				continue;
			}
		}
		

	}
	
	
	
	//오름차 순 정렬
	int trans = 0;
	for (int row = 1; row < dange-1; row++) {
		for (int col = row+1; col < dange-1-row; col++) {
			if (dange_map[col]> dange_map[col+1]) {
				trans = dange_map[col];
				dange_map[col] = dange_map[col+1];
				dange_map[col+1] = trans;
			}
		}
		
	}

	//결과 출력
	printf("%d\n", dange);
	for (int d = 0; d < dange; d++) {
		printf("%d\n",dange_map[d]);
	}

	

	return 0;


}


//들어온 인덱스(원형) 상태 확인 및 상하좌우확인
void dfs(int nowrow, int nowcol, int dange, int n) {
	dange_map[dange]++;
	visited[nowrow][nowcol] = 1;
	map[nowrow][nowcol] = dange;
	
	for (int i = 0; i < 4; i++)
	{
		int n_i = nowrow + xasis[i]; // 다음에 탐색할 위치의 좌표
		int n_j = nowcol + yasis[i];

		if (0 <= n_i && n_i < n && 0 <= n_j && n_j < n) // 범위  확인(0 ~ n-1)
			if (map[n_i][n_j] == 1 && visited[n_i][n_j] == 0) // 단지가 존재하고 방문하지 안았을 경우만
				dfs(n_i, n_j, dange, n); // 탐색하기(재귀)
	}
	return;

	
}