2667. 단지번호붙이기

이 문제는 전형적인 DFS/BFS 완전탐색 문제이다. 

 

Solution 

 

1. 값을 입력 받는다. 여기서 값이 1인 인덱스를 벡터 stack에 입력한다.
2. 벡터 stack이 빌때까지 while문을 돌면서 dfs 함수를 호출한다. 
3. 호출할 때는 새로운 단지를 발견한 것이기에 answer함수에 새로운 단지를 찾았다는 뜻으로 push_back으로 값을 넣어준다. 
4. dfs함수에서는 4방향을 보며 1일 경우, 재귀호출을 해준다.  => 여기서 유의점은 범위체크이다. 인덱스가 배열을 범위를 넘어서면 무조건 오류가 나기때문에 귀찮더라도 범위체크를 해줘야한다. 
5. 재귀호출하면서 집의 갯수를 세야된다. 그렇기에 새로운 집에 방문할때마다 answer의 마지막 요소에 +1를 해준다. 여기서 왜 마지막 요소인가하면, 동시에 여러단지를 검색하지않기 때문이다. 그렇기에 집이 포함된 단지는 무조건 맨 마지막 단지이다. 
6. 이렇게 단지를 다 세고 나면 answer.size()가 단지의 갯수가 된다.
7. 오름차순 정렬은 sort를 이용하여 해주었다. 

Key Point

범위 체크를 유의하자!

이 문제는 비교적 쉬운 문제였지만, 푸는데 오랜 시간이 걸렸다. 그 이유는 행렬을 받아올 때, 값과 값 사이에 space가 없어서 하나의 int 변수로 받아진다는 것이었다. 그래서 나는 int변수를 %와 /를 이용해서 값을 분리해줬다. 하지만, 여기서 문제가 발생하였다. int형 변수의 최대범위는 10^10이다. 이는 10자리수를 최대로 표현할 수 있다는 말이다. 그렇기 때문에 행렬의 최대크기인 25를 받기에는 부족하다. 25자릿수를 받을려면 long long 형 변수도 불가능하여 char로 하나한 받는 방식으로 변경하였다.  => 데이터형의 최대범위를 체크하자!

4방향을 검색할 때, dx,dy처럼 배열을 이용하자!

 

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

typedef struct A {
	int i;
	int j;
};
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
int map_size = 0;

int map[50][50] = { 0 };
vector<int> answer;
void dfs(int i, int j) {
	answer[answer.size()-1]++;
	map[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] < map_size && j + dy[k] >= 0 && j + dy[k] < map_size) {
			if (map[i + dx[k]][j + dy[k]] == 1) {
				dfs(i + dx[k], j + dy[k]);
			}
		}
	}
}


int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);


	cin >> map_size;
	vector<A> stack;
	for (int i = 0; i < map_size; i++) {
		char a=0;
		for (int j = 0; j<map_size; j++) {
			cin >> a;
			map[i][j] = a-'0';

			if (map[i][j] == 1) {
				stack.push_back({ i,j });
			}
		}
	}
	while (!stack.empty()) {
		int i = stack.back().i;
		int j = stack.back().j;
		stack.pop_back();
		if (map[i][j] ==1) {
			answer.push_back(0);
			dfs(i, j);
		}
	}
	sort(answer.begin(), answer.end());
	cout << answer.size() << endl;
	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << endl;
	return 0;
}

 

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

2667번: 단지번호붙이기