[백준 2667] 단지번호붙이기

사실 이 문제는 BFS DFS 둘 다 되지만 DFS로 풀어보았다

 

---

[ 첫번째 시도 ]

int dfs(int starty, int startx) {
	stack<pair<int, int>> s;
	s.push(make_pair(starty, startx));
    
	int y, x, cnt = 0;

	while (!s.empty()) {
		y = s.top().first;
		x = s.top().second;
        
		s.pop(); 
        	map[y][x] = 0; 
        	cnt++;

		if (y + 1 < N && map[y + 1][x]) s.push(make_pair(y + 1, x));
		if (x + 1 < N && map[y][x + 1]) s.push(make_pair(y, x + 1));
		if (y - 1 >= 0 && map[y - 1][x]) s.push(make_pair(y - 1, x));
		if (x - 1 >= 0 && map[y][x - 1]) s.push(make_pair(y, x - 1));
	}
	return cnt;
}

 

맨 처음 만든 함수이다.

 

하지만 이는 치명적인 결함이 있다

바로 중복카운팅이 된다는 것이다

( 방문 경로를 출력해보면 중복되는 경로들이 나온다 )

 

map[y][x] = 0; 을 통해 visited 했다고 map을 최신화하는 작업을 pop 한 뒤에 하게끔 했는데

이러면 중복카운팅이 일어날 수 있다.

 

따라서 stack에 push할때 visited 했다고 최신화를 해줘야한다

 

그래서 map[y][x]=0  코드의 위치만 바꾸면 아래와 같이 나온다

 

---

[ 두번째 시도 ]

int dfs(int starty, int startx) {
	stack<pair<int, int>> s;
	s.push(make_pair(starty, startx));
	map[starty][startx] = 0; // 시작점은 예외적으로 처리
    
	int y, x, cnt = 0;

	while (!s.empty()) {
		y = s.top().first;
		x = s.top().second;
		
		s.pop();
		cnt++;

		if (y + 1 < N && map[y + 1][x]) { s.push(make_pair(y + 1, x)); map[y+1][x] = 0; }
		if (x + 1 < N && map[y][x + 1]) { s.push(make_pair(y, x + 1)); map[y][x+1] = 0; }
		if (y - 1 >= 0 && map[y - 1][x]) { s.push(make_pair(y - 1, x)); map[y-1][x] = 0; }
		if (x - 1 >= 0 && map[y][x - 1]) { s.push(make_pair(y, x - 1)); map[y][x-1] = 0; }
	}
	return cnt;
}

 

위와 같이 바꾸면 시작점 map[starty][startx] 는 while문 내 if문을 통해 다시 방문되면 안된다

왜냐하면 그렇게 되면 중복처리이기 때문이다.

 

따라서 예외적으로 =0 처리를 해줘야한다

	s.push(make_pair(starty, startx));
	map[starty][startx] = 0; // 시작점은 예외적으로 처리

 

이게 실제로 어떤 문제는 맨 첫번째 코드와 같이 해도 아무 문제가 없다.

하지만 이 문제와 같이 DFS 원소 개수를 카운팅하는 문제는 중복이 있으면 답이 틀릴 수 밖에 없다

 

그래서 최대한 오류가 나지 않는 두 번째 코드로 작성하도록 연습하는게 좋다

 

마지막은 풀코드 ㅇㅇ

---

[ main ]

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

#define SIZE 25

using namespace std;

int map[SIZE][SIZE];
int N;

int dfs(int starty, int startx) {
	stack<pair<int, int>> s;
	s.push(make_pair(starty, startx));
	map[starty][startx] = 0;

	int y, x, cnt = 0;

	while (!s.empty()) {
		y = s.top().first;
		x = s.top().second;
		
		s.pop(); cnt++;

		if (y + 1 < N && map[y + 1][x]) { s.push(make_pair(y + 1, x)); map[y+1][x] = 0; }
		if (x + 1 < N && map[y][x + 1]) { s.push(make_pair(y, x + 1)); map[y][x+1] = 0; }
		if (y - 1 >= 0 && map[y - 1][x]) { s.push(make_pair(y - 1, x)); map[y-1][x] = 0; }
		if (x - 1 >= 0 && map[y][x - 1]) { s.push(make_pair(y, x - 1)); map[y][x-1] = 0; }
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	char ch;
	vector<int> v;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> ch; map[i][k] = (int)(ch-'0');
		}
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (map[i][k]) v.push_back(dfs(i, k));
		}
	}
	
	sort(v.begin(), v.end());
	cout << v.size() << "\n";
	for (auto it = v.begin(); it != v.end(); it++) { cout << *it << "\n"; }
	return 0;
}