[백준] 2667번 단지 번호 붙이기 (C++, JAVA)

2667번: 단지번호붙이기

같은 단지인 애들을 BFS로 찾아준 다음

집의 수를 카운트 해주고 단지 배열에 넣어준다.

 

이차원 배열을 돌면서 값이 1인 곳이 있으면 그걸 시작으로

해당 위치의 상하좌우의 값이 1이면 큐에 그 위치를 넣어놓고

큐가 empty할 때까지 반복해주는 BFS함수를 만들면 된다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

int cnt = 0, town[625] = { 0 };
void Bfs(int i, int j, int N, int map[][26]) {
	queue <pair<int, int>> q;
	q.push(pair<int, int>(i, j));
	int x, y;
	map[i][j] = 0;
	while (!q.empty()) {
		x = q.front().first, y = q.front().second;
		if (x - 1 >= 0 && map[x - 1][y]) {
			q.push(pair<int, int>(x - 1, y));
			map[x - 1][y] = 0;
			cnt++;
		}
		if (x + 1 < N && map[x + 1][y]) {
			q.push(pair<int, int>(x + 1, y));
			map[x + 1][y] = 0;
			cnt++;
		}
		if (y - 1 >= 0 && map[x][y - 1]) {
			q.push(pair<int, int>(x, y - 1));
			map[x][y - 1] = 0;
			cnt++;
		}
		if (y + 1 < N && map[x][y + 1]) {
			q.push(pair<int, int>(x, y + 1));
			map[x][y + 1] = 0;
			cnt++;
		}
		q.pop();
	}
}

int main() {
	int N;
	cin >> N;
	string a;
	int map[26][26] = { 0 };
	for (int n = 0; n < N; n++) {
		cin >> a;
		for (int i = 0; i < a.size(); i++) map[n][i] = a[i] - '0';
	}
	
	int idx = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) {
				cnt = 1;
				Bfs(i, j, N, map);
				town[idx] = cnt;
				idx++;
			}
		}
	}

	sort(town, town + idx);
	cout << idx << "\n";
	for (int i = 0; i < idx; i++) cout << town[i] << "\n";

	return 0;
}

 

< JAVA 코드 >

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_2667_단지번호붙이기 {
	private static int N, tmp, tot = 0;
	private static int arr[][], res[], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	
	public static void dfs(int X, int Y) {
		arr[X][Y] = 0; // 이제 다시는 비교할 필요 없음
		for(int i = 0; i < 4; i++) {
			int x = X + dx[i], y = Y + dy[i];
			if(x < 0 || x >= N || y < 0 || y >= N || arr[x][y] == 0) continue;
			arr[x][y] = 0;
			res[tot]++;
			dfs(x, y);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N][N]; res = new int[N * N];
		for(int i = 0; i < N; i++) {
			String st = sc.next();
			for(int j = 0; j < N; j++) arr[i][j] = st.charAt(j) - '0';
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(arr[i][j] == 0) continue;
				dfs(i, j);
				res[tot++]++;
			}
		}
		System.out.println(tot);
		res = Arrays.copyOf(res, tot);
		Arrays.sort(res);
		for(int i = 0; i < tot; i++) System.out.println(res[i]);
	}
}