백준 2667 C++ - 단지번호붙이기

Intro

문제해결 및 소스코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/*									<문제해결>
				규칙1. 지도에서 집이있는곳은 1이고, 집이없는곳은 0이다.
				규칙2. 집이 상하좌우로 연결되어있으면 같은단지이다.

				이 문제를 해결하려면 DFS 또는 BFS 알고리즘을 사용하면된다. 나는 DFS 알고리즘을 사용하여 문제를 해결했다.

            가장왼쪽위 map[0][0]
				---- +y ---->
			|	0 1 1 0 1 0 0		예시 지도는 왼쪽과같다. 지도를 map 배열에 저장하고, 집이 있는곳에서 
			|	0 1 1 0 1 0 1		DFS를 호출하여 상하좌우를 탐색하며 연결된 집이 있는지 확인한다.
			|	1 1 1 0 1 0 1		
			+x	0 0 0 0 1 1 1		
			|	0 1 0 0 0 0 0       * 만약 연결된 집이 있다면, 같은단지임을 표시하고 같은단지에있는 
			|	0 1 1 1 1 1 0       집수를 증가시킨다. 그리고 그 위치에서 다시한번 DFS를 호출하여 더이상 
			v	0 1 1 1 0 0 0       나아갈 수 없을때까지 반복한다.
*/


vector<int> map[26];			// .. 지도를 저장할 변수
vector<int> result;				// .. 단지별 집갯수를 저장할 변수

bool visited[26][26];			// .. 방문여부
int label = 0;					// .. 단지번호
int cnt = 0;					// .. 집 갯수
int n;							// .. 지도의 크기(n x n)

// 상 하 좌 우 방향배열
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };


void DFS(int x, int y)
{
	visited[x][y] = true;		// 해당위치 방문기록
	map[x][y] = label;			// 해당위치 단지번호 매기기
	cnt++;						// 해당단지 집 갯수 증가

	// 상하좌우 순서로 탐색
	for (int i = 0;i < 4;i++)
	{
		int nextDirX = x + dx[i];		
		int nextDirY = y + dy[i];

		// 지도 범위를 벗어난 탐색은 무시
		if (nextDirX < 0 || nextDirY < 0 || nextDirX >= n || nextDirY >= n)
			continue;

		// 탐색한곳이 방문하지 않은곳이고, 집이 있는곳일때
		if (!visited[nextDirX][nextDirY] && map[nextDirX][nextDirY] == 1)
			DFS(nextDirX, nextDirY);
	}
}

int main()
{
    // 지도 크기 입력
	cin >> n;			

	// 지도 입력
	for (int i = 0;i < n;i++)
	{
        // 공백없이 주어진 입력을 처리하기위해 string 변수로 입력받음
		string input;
		cin >> input;

        // 지도채워넣기
		for (int j = 0;j < input.length();j++)
		{
			if (input[j] == '1') map[i].push_back(1);
			else map[i].push_back(0);
		}
		
	}
	
    // map[0][0]부터 가로축부터 탐색
	for (int i = 0;i < n;i++)			// 세로축 증가
	{	
		for (int j = 0;j < n;j++)		// 가로축 증가
		{
			if (map[i][j] == 1 && visited[i][j] == false)	// 집이있고 방문하지않은곳
			{
				DFS(i, j);
				label++;				// 다음 단지번호
				result.push_back(cnt);	// 집 갯수 저장
				cnt = 0;				// 집 갯수 초기화
			}
		}
	}
	
	// 정답 오름차순 정렬
	sort(result.begin(), result.end());

	// 총 단지수 및 단지별 집 수 출력
	cout << label << "\n";
	for (int i = 0;i < result.size();i++)
	{
		cout << result[i] << "\n";
	}
}