알고리즘: 백준 2667번 단지번호붙이기 (feat. c++)

백준 2667번 링크입니다. 

2667번: 단지번호붙이기

 

 

bfs 너비 우선 탐색을 이용하여 단지수를 찾는다.

 

방문한 집은 방문처리를 함으로써

 

반복문을 이용해 모든 집을 방문하면서 방문처리가 되어있는 주택은 패스,

 

방문하지 않은 집은 bfs를 시행한다. 

 

 

 

총 단지수를 받을 house와 방문한 곳을 표시하는 visit을 만들었다.

 

방문했으면 visit의 해당하는 인덱스에 1을 집어 넣고, 아니면 0을 넣는다.

 

bfs하기 전, 초기 visit[y][x] 값은 house[y][x]가 0 일때 1, 1일때 0으로 초기화한다. 

(반복문으로 모든 집을 방문했을 때 모든 visit값은 1이다)

 

 

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

using namespace std;

int house[25 + 1][25 + 1];  //입력받을 지도
int visit[25 + 1][25 + 1];  //방문처리여부
int total = 0;              // 총 단지수
int N;                      // 지도의 크기

bool check(int x, int y) {  //y행 x열로 이동 가능여부

	if (x < 1 | x > N | y < 1 | y > N) return false;   // 범위를 벗어나면 false
	if (visit[y][x] == 1) return false;    // 이미 방문했으면 false
	if (house[y][x] == 0) return false;    // 주택이 없으면 false

	return true;
}

int bfs(int y, int x) {
	
	if (visit[y][x] == 1) return 0;  //이미 방문했으면 0을 리턴
	
    int count = 0;  // 단지내 주택수
    total += 1;     // 단지 수 카운트
	queue<int> qx, qy;  
	qx.push(x);
	qy.push(y);
	
	
    
	while (!qx.empty() | !qy.empty()) {  // qx와 qy가 빌때까지 반복한다. 
		int cqx = qx.front(); qx.pop();
		int cqy = qy.front(); qy.pop();
		
		if (visit[cqy][cqx]) continue;  //방문했으면 넘어간다. 
            
		count += 1;  //방문하지 않은 주택 카운트
        
		visit[cqy][cqx] = 1;  //방문처리



		if (check(cqx, cqy - 1)) {  //위로 이동
			qx.push(cqx);
			qy.push(cqy - 1);
			}

		if (check(cqx, cqy + 1)) {  //아래로 이동
			qx.push(cqx);
            qy.push(cqy + 1);			
		}

		if (check(cqx - 1, cqy)) {  //좌측으로 이동
			qx.push(cqx - 1);
            qy.push(cqy);
		}
        
		if (check(cqx + 1, cqy)) {  //우측으로 이동
			qx.push(cqx + 1);
            qy.push(cqy);
		}
		



	}

	return count;
}


int main() {

	vector<int> bfs_list; // 단지당 주택수를 담을 벡터리스트
	
	scanf("%d", &N); 
	for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++)
	{
		scanf("%1d", &house[i][j]);  
		if (house[i][j] == 1) visit[i][j] = 0;
		if (house[i][j] == 0) visit[i][j] = 1;
	}

	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++) {
			int x = bfs(i, j);
			if (x == 0)
				continue;
			else
				bfs_list.push_back(x);
		}
		
	}


	printf("%d\n", total);
	sort(bfs_list.begin(), bfs_list.end());
	for (int i = 0; i < bfs_list.size(); i++) printf("%d\n", bfs_list[i]);
	
	return 0;
}