백준 2667번 - 단지번호붙이기 DFS풀이

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제와 입력예제는 링크로 대체합니다.

 

dfs와 bfs방식 모두 풀 수 있는 문제인데요. 저는 dfs방식으로 풀었습니다. 

입력으로 주어지는 맵 정보를 2차원배열에 저장하고 방문여부를 저장할 동일한 크기의 배열을 사용하였습니다. 

 

그리고 각 단지의 크기를 저장하기 위해 1차원 배열을 사용하였는데 이 때 이 배열의 크기로 문제에서 나올 수 있는 가장 많은 단지의 수로 설정해애 합니다. 단지 최대 개수는 문제에서 대각선의 경우 같은 단지로 보지 않는다고 하였으므로 모든 빌딩이 격자무늬 형태로 존재하는 경우입니다. 예를들면

10101

01010

10101

01010

10101

같은 형식일 때 단지의 개수는 최대입니다. 따라서 n*n/2+1개보다 단지의 수는 많아질 수 없습니다.

단지의 건물개수를 저장할 일차원 배열의 크기를 n*n/2+1로 선언합니다.

 

입력을 받아 정보를 저장한 뒤, 순차적으로 각 자리의 값이 1이고 이전에 방문한 곳이 아닐 경우 dfs함수를 호출하여 인접하여 있는 모든 구역을 dfs함수를 재귀 호출하여 한 단지의 건물 개수를 구합니다.

그리고 한 단지의 개수를 구하는 dfs가 끝나면 단지개수를 증가시키고 모든 탐색이 끝난 후 STL의 sort함수를 이용하여 정렬한 후 출력하였습니다. 소스 코드는 다음과 같습니다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>

using namespace std;
int map[25][25];
int visit[25][25];
int block[313];
int block_num;
int N;

int index[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };//아래 오른쪽 위 왼쪽 순서대로

void dfs(int x, int y) {
	visit[x][y] = 1;
	block[block_num]++;
	//printf("%d %d\n", x, y);
	for (int i = 0; i < 4; i++) {
		int Xidx = x + index[i][0];//아래 오른쪽 위 왼쪽 순서대로 인덱스 생성.
		int Yidx = y + index[i][1];
		if (Xidx < 0 || Yidx < 0 || Xidx >= N || Yidx >= N)
			continue;
		if (map[Xidx][Yidx] == 1 && visit[Xidx][Yidx] == 0) {
			dfs(Xidx, Yidx);//방문한칸이 아니면 재귀호출
		}
	}
}

void sort() {

}

int main()
{
	block_num = 0;
	scanf("%d", &N);
	getchar();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char input;
			scanf("%c", &input);
			if (input == '0')
				map[i][j] = 0;
			else
				map[i][j] = 1;

		}
		getchar();
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1 && visit[i][j] == 0) {
				dfs(i, j);
				block_num++;
			}
		}
	}

	printf("%d\n", block_num);
	sort(block, block + block_num);
	for (int i = 0; i < block_num; i++) {
		printf("%d\n", block[i]);
	}
}

도움이 되셨다면 좋아요 한번 부탁드립니다~