[Baekjoon][C++] 2667번 단지번호붙이기 문제설명 및 코드

▷ 문제설명

2667번: 단지번호붙이기

집이 있는 곳은 1, 집이 없는 곳은 0으로 표현된 지도정보(정사각형)를 주고,

단지의 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제

 

조건) 연결된 집들은 상하좌우에 있는 집이다. 대각선 X.

        지도의 크기 N은 5<=N<=25 범위의 수이다.

 

▷ 문제풀이

[ 변수정의 ]

문제에서 지도 정보를 N*N크기로 줬으므로 배열을 이용해서 입력 받았고, 방문 배열 또한 배열로 표현했다.

해당 지점에서 상하좌우를 탐색하기 위한 변수로 direction[4][2] 변수를 만들었다.

 

[ 알고리즘 - DFS이용 ]

1) 지도정보는 scanf로 공백없는 숫자를 한줄씩 입력받는다. scanf_s("%1d", &map[i][j])

2) 지도의 (0, 0) 좌표부터 집이 있는 자리이고 방문한 적 없는 곳이면 집을 탐색하기 시작한다.

3) 현재 위치(0, 0)에서 상하좌우를 살펴본다. 상하좌우(반복문으로 총 4번)를 탐색할 땐 지도의 범위를 넘지 않는 경우만 탐색한다.

if (dx >= 0 && dx < map_size && dy >= 0 && dy < map_size)

4) 탐색할 때마다 현재 위치를 방문했다고 표시해주고(visited[x][y] = 1) 단지내 집의 수를 늘려준다(houseNum++).

5) 이동한 상 or 하 or 좌 or 우 좌표 위치가 집이 아니거나 방문한적이 있을 때까지 깊이 탐색한다. SearchHouse(dx, dy)

6) 집이 아니거나 방문한적이 있으면 return한다.(이전 단계로 돌아감) if (map[x][y] == 0 || visited[x][y])

7) 돌아와서 단지내 집의 수를 관리하는 벡터배열(vector<int> houseGroup)에 넣어준다.

7) 연결된 단지 내에서 DFS로 모두 탐색했으면 단지의 수를 1 늘려준다. houseGroupNum++

8) 마지막 지도 좌표까지 탐색을 하면 단지 수와 각 단지내 집의 수를 오름차순(sort() 함수 이용)으로 출력한다.

 

 

▷ 시간복잡도

지도 크기만큼 2중 반복문을 돌리고,  각 자리마다 4번씩 탐색하므로 O(4N²) = O(N²)의 시간복잡도를 갖는다.

 

▷ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 26;

void SearchHouse(int, int);

int map[MAX][MAX];
bool visited[MAX][MAX];

int map_size;
int direction[4][2] = { {0,-1}, {1,0}, {-1,0}, {0,1}, }; //상하좌우
int houseGroupNum;	//단지수
int houseNum;		//단지내의 집 수

int main() {
	//Input
	cin >> map_size;
	for (int i = 0; i < map_size; i++) {
		for (int j = 0; j < map_size; j++) {
			scanf_s("%1d", &map[i][j]); // 공백없는 숫자를 한줄씩 입력받는 법
		}
	}

	//Search
	vector<int> houseGroup;
	for (int i = 0; i < map_size; i++) {
		for (int j = 0; j < map_size; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				SearchHouse(i,j);
				houseGroup.push_back(houseNum);
				houseGroupNum++;
				houseNum = 0;
			}
		}
	}

	//Output
	cout << houseGroupNum << "\n";
	sort(houseGroup.begin(), houseGroup.end());
	for (int i = 0; i < houseGroup.size(); i++) {
		cout << houseGroup[i] << "\n";
	}
}

void SearchHouse(int x, int y) {
	if (map[x][y] == 0 || visited[x][y]) {
		return;
	}

	visited[x][y] = 1;
	houseNum++;

	for (int i = 0; i < 4; i++) {
		int dx = x + direction[i][0];
		int dy = y + direction[i][1];
		if (dx >= 0 && dx < map_size && dy >= 0 && dy < map_size) {
			SearchHouse(dx, dy);
		}
	}
}