2667.단지번호붙이기

이번에 풀어볼 문제는 단지번호붙이기이다.

2667번: 단지번호붙이기

생각보다 이상한곳에 막혀서 시간낭비를 했다. 시간은 1시간 30분정도 걸렸고 목표한 시간보다 30분이나 초과되었다.

사실 30분컷 낼 수 있었는데 이걸 코드하나를 잘못집어넣어서 하루종일 걸렸다.. 후... 

DFS를 이용해서 풀었고 이 문제의 포인트는 Stack를 이용하되 Stack에 자신이 이동한 부분의 좌표를 넣어주는 것이다.

그래야지 DFS로 쭈욱 탐색하다가 막혔을 때 다시 돌아가서 탐색하지 않은 방향으로 탐색을 진행할 것이다.

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX 26

using namespace std;

bool check[MAX][MAX];
int map[MAX][MAX];
int n;
int dx[4] = { -1, 1, 0, 0 }; //이동 x좌표
int dy[4] = { 0, 0, -1, 1 }; //이동 y좌표

stack <pair<int, int>>ss;

int dfs(){
	int x = ss.top().first; // stack의 x좌표 사용
	int y = ss.top().second;// stack의 y좌표 사용
	check[x][y] = true; 첫 시작구간은 들렸으므로 true로 체크
	int cnt = 1; // 몇개의 단지가 존재하는지 세는 변수
	while (!ss.empty()){ // stack이 빌 때까지
		for (int i = 0; i < 4; i++){ //좌표 이동 후 탐색을 위한 for문
			int ax = x+dx[i]; // 선택한 좌표에서 x좌표이동 탐색
			int ay = y+dy[i]; // 선택한 좌표에서 y좌표이동 탐색

			if (ax < 0 || ay <0 || ax>n || ay>n) //좌표가 map 벗어나지면
				continue; // 넘어간다.

			if (!check[ax][ay] && map[ax][ay] == 1){ //미탐색 && 단지존재
				check[ax][ay] = true; // 탐색으로 체크
				ss.push(make_pair(ax, ay)); // 탐색한 부분 stack에 push
				x = ss.top().first; //해당좌표로 이동하기위함
				y = ss.top().second;//해당좌표로 이동하기위함
				i = -1; // 이동한채로 다시 탐색하기위함
				cnt++;  // 단지 ++
			}
		}
		if (!ss.empty()){ //스택이 안비었다면 스택의 top으로 할 수있는 탐색 끝났으므로
			ss.pop(); //탐색끝난 좌표 pop
			if (!ss.empty()){ //그래도 남았다면 이전의 스택에서 미탐색 좌표가 있을지모르니
				x = ss.top().first; // 해당 좌표로 다시돌아가 4방향탐색
				y = ss.top().second;
			}
		}
	}
	return cnt; // 단지 숫자를 리턴해줌
}

int main() {
	cin >> n;
	int cnt = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	vector<int>v;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (map[i][j] == 1 && !check[i][j]){ // 미탐색 && 단지존재 
				ss.push(make_pair(i, j)); // 스택에 해당 좌표 넣음
				v.push_back(dfs()); // dfs 진행 후 return값 vector에 저장
			}
		}
	}
	sort(v.begin(), v.end()); // 오름차순 정렬
	cout << v.size() << "\n"; // 백터 크기 출력
	for (int i = 0; i < v.size(); i++){ // 단지 숫자들 하나씩 출력
		cout << v[i] << "\n";
	}


	return 0;
}