[BFS] 백준 2667번 단자번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

수행기간 : 2021/01/18~01/19

이 문제는 지금까지 풀었던 DFS&BFS 보단 확실히 난이도가 있는 문제로 보였다. solved.ac 에 가서 난이도를 찾아보니 역시 실버1.. 사실 나는 아직 실버 1이나 골드5를 풀기에는 조금 벅차다. 그래도 이건 저번주에 풀었던 미로찾기를 응용한 버전이라고 생각하여 쭉 풀어나갔다. BFS구현은 쉬웠지만 "0을 경계로 단지를 어떻게 구분해야 할까" 여기서 너무 오래 시간이 끌려버렸다. 사실 생각하면 너무 쉽다... main문에서 map이 1일때 탐색을 해주는 조건문을 만들면 되는 것이였다.

너무 어렵게 생각하기보단 기술적인 부분을 나올때마다 숙지하고 넘어가면 나중엔 이런 수준에 문제도 쉽게 풀 수 있을것 같다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
#include<algorithm>
using namespace std;
//vector< vector<int>> map;
//vector< vector<int>> visit;
int map[101][101];
int visit[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue <pair<int, int>> q;
int cnt = 0;
int dan[1000] = { 0, };
int n;
int index = 0;

void bfs(int a, int b) {
	visit[a][b] = 1;
	cnt++;
	q.push(make_pair(a, b));
	while (!q.empty()) {
		int nowA = q.front().first;
		int nowB = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int nx = nowA + dx[i];
			int ny = nowB + dy[i];
			if ((nx >= 0 && nx <= n) && (ny >= 0 && ny <= n)) {
				if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visit[nx][ny] = 1;
					cnt++;
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		for (int j = 0;j < n;j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < n;j++) {
			if (map[i][j] == 1 && visit[i][j] == 0) {
				bfs(i, j);
				dan[index++] = cnt;
				cnt = 0;
			}
		}
	}
	sort(dan, dan + index);
	if (n >= 5 && n <= 25) {
		cout << index << "\n";
		for (int i = 0;i < index;i++) {
			cout << dan[i] << "\n";
		}
	}
	return 0;
}