백준 : 2667번, 단지번호붙이기

문제 주소 : www.acmicpc.net/problem/2667

정답 비율 : 39.120% (2021.05.02 11:59 기준)

2667번: 단지번호붙이기

문제 요약:

NxN크기의 배열이 주어질 때 1은 집이 있는 곳, 0은 집이 없는 곳이라고 할 때 상하좌우로 연결된 집들을 하나의 단지라고 할 때 단지의 개수와 각 단지의 크기(집의 개수)를 구하는 문제입니다.

 

문제 조건:

입력 : 첫 줄 N 이어서 N개줄에 길이가 N이고 0와 1로 이루어진 문자열이 주어집니다.

출력 : 총 단지수를 출력 후에 각 단지의 크기를 오름차순으로 출력하시오.

시간 : 1초

 

문제 풀이:

BFS(or DFS) + 정렬을 합친 문제입니다.

 

이 때 N의 최대 크기가 25이므로 단지의 최대 크기는 625로 큰 수가 아니므로 정렬 시간이 O(N) 걸리는 Counting Sort를 사용하였습니다. 

 

코드는 다음과 같습니다.

 

C99

// solve 2667
#include<stdio.h>

int result[625];
int count = 0;
int length;

void dfs(char map[][25], int x, int y, int* ans) {
	*ans += 1;

	map[y][x] = '0';
	int d_x[4] = { 1, -1, 0, 0 };
	int d_y[4] = { 0, 0, 1, -1 };

	for (int i = 0; i < 4; i++) {
		int t_x = x + d_x[i];
		int t_y = y + d_y[i];

		if (t_x >= 0 && t_x < length && t_y >= 0 && t_y < length && map[t_y][t_x] == '1') {
			dfs(map, t_x, t_y, ans);
		}
	}

}

int main(void){
	char str[26][26];

	scanf("%d", &length);

	for (int i = 0; i < length; i++) {
		scanf("%s", str[i]);
	}

	for (int i = 0; i < length; i++) {
		for (int j = 0; j < length; j++) {
			if (str[i][j] == '1') {
				int ans = 0;
				dfs(str, j, i, &ans);
				count++;
				result[ans - 1]++;
			}
		}
	}

	printf("%d\n", count);
	for (int i = 0; i < 625; i++) {
		for (int j = 0; j < result[i]; j++)
			printf("%d\n", i + 1);
	}

	return 0;
}

 

Python3

# solve 1920
import sys

sys.setrecursionlimit(10 ** 8)

Max = int(input())
map = [list(input()) for i in range(Max)]
result = []


def dfs(x, y, ans):
    map[y][x] = '0'
    ans += 1

    if 0 < y and map[y - 1][x] == '1':
        ans += dfs(x, y - 1, 0)
    if y < Max - 1 and map[y + 1][x] == '1':
        ans += dfs(x, y + 1, 0)
    if 0 < x and map[y][x - 1] == '1':
        ans += dfs(x - 1, y, 0)
    if x < Max - 1 and map[y][x + 1] == '1':
        ans += dfs(x + 1, y, 0)
    return ans


for i in range(Max):
    for j in range(Max):
        if map[i][j] == '1':
            ans = dfs(j, i, 0)
            result.append(ans)

result.sort()

print(len(result))

while result:
    print(result.pop(0))

 

***

정보 올림피아드 초등부 문제라니 더 분발해야겠습니다.