백준 2667 단지번호 붙이기

2차원 배열을 0,0부터 순차적으로 탐색하다가

집을 만나면 그 집을 루트로 하여 BFS를 시작한다

이 문제에서 약간 다른점은 굳이 isVisit를 쓸 필요가 없다는 것이다.

arr[i][j]에서 이미 단지 번호를 붙였고

단지 번호가 붙여져있다는 것은 이미 방문했다는 뜻이니까

isVisit로 방문한지 체크하지 않고 단지 번호가 붙여져있는 것으로 방문한지 체크하면 되기 때문

그 외에 

단지 번호를 0부터 붙이고 싶어서

빈땅, 집이 있지만 단지 번호가 붙여지지 않은 집, 단지 번호가 붙여진 집

을 서로 구분하기 위해서

입력을 받을때

0과 1로 받지 않고

-2와 -1로 받았다.

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

using namespace std;
int N;
int arr[26][26];
vector<int> houses;

int di[4] = { -1,0,1,0 };
int dj[4] = { 0,-1,0,1 };

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < N; j++) {
			arr[i][j] = temp[j] - 50; //-2은 빈땅, -1은 집이 있음
		}
	}

	int totalHousesNum = 0;

	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (arr[i][j] == -1) {
				queue<pair<int, int>> bfs;
				bfs.push(make_pair(i, j));

				totalHousesNum++;
				arr[i][j] = totalHousesNum;
				houses.push_back(1);

				int nowi, nowj;
				while (!bfs.empty()) {
					nowi = bfs.front().first;
					nowj = bfs.front().second;
					bfs.pop();

					for (int r = 0; r < 4; r++) {
						int nexti = nowi + di[r];
						int nextj = nowj + dj[r];
						if (nexti < 0 || nexti >= N || nextj < 0 || nextj >= N) continue;
						if (arr[nexti][nextj] == -1) { //아직 방문 하지 않은, 집이 있는 노드
							bfs.push(make_pair(nexti, nextj));
							arr[nexti][nextj] = totalHousesNum; //집에 단지 번호를 붙이고
							houses[totalHousesNum - 1]++;  // 단지에 소속된 집의 수를 늘림
						}
					}
				}

			}
		}
	}


	sort(houses.begin(), houses.end());

	cout << totalHousesNum << endl;
	for (int i = 0; i < totalHousesNum; i++) {
		cout << houses[i] << endl;
	}

	return 0;
}

2차원 배열이 그래프가 될때

pair말고 더 좋은 방법 없을까..

해싱은 짜다가 햇갈리기 쉬울거 같고..