[백준] 알고리즘 2667번 - 단지번호붙이기문제

문제

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

2667번: 단지번호붙이기

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n,cnt;
int arr[26][26];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool check[26][26];
vector<int> ans;
queue<pair<int,int>> qu;
void bfs(int x, int y) {
	qu.push({ x,y });
	cnt++;
	check[x][y] = true;
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx<0 || nx>n - 1 || ny<0 || ny>n - 1) continue;
			if (arr[nx][ny] == 1 && !check[nx][ny]) {
				check[nx][ny] = true;
				qu.push({ nx,ny });
				cnt++;
			}
		}
	}
}
int main() {
	//ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1&&!check[i][j]) {
				bfs(i, j);
				ans.push_back(cnt);
				cnt = 0;
			}
		}
	}
	sort(ans.begin(), ans.end());
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) printf("%d\n",ans[i]);
}

해설

우선 입력에서 공백이없는 숫자나 문자가 주어질 경우 scanf를 이용해서 string 형식으로 굳이 입력받지 않고 바로 int형으로 저장할 수 있다. 다만 주의해야하는점은 scanf를 사용하면 cin,cout을 중복으로 사용할 수 없다. printf로 출력을 해주자.

 

문제는 딱 보기만해도 bfs나 dfs로 해결하면 쉽게 해결될 문제처럼 생겼다.

직사각형 정사각형 안에서 문제를 해결하라 하면 브루트포스 아니면 bfs나 dfs를 먼저 유추해내보자.

아파트단지를 전체를 순회해야 결과를 알 수 있으므로 bfs나 dfs를 사용해보자.

우선 0이면 방문을 하지않고 1인경우 bfs나 dfs의 함수를 호출한다.

이제 1과 위 아래 오른쪽 왼쪽을 다 탐색하여 계속해서 1이 나올때까지 탐색을하고 종료되면, 하나의 단지를 다 탐색한 것이다.

소스코드를 보며 이해를 해봅시다.

위에는 bfs 소스를 올려뒀으며, dfs 소스도 같이 첨부하겠습니다. 두개다 연습하여 둘 다 마스터할때까지 같이 구현해보도록 합시다.

https://github.com/kitten-master/algorithm/commit/709543769a77c33aa7b7ec897be18781a26c0e25

단지번호붙이기(bfs add) · kitten-master/algorithm@7095437