백준 알고리즘 2667 (단지번호붙이기) - C++, Python

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

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

2667번: 단지번호붙이기

 

N x N 배열에 0 또는 1의 숫자가 적혀있다.

여기서, 1이 상하좌우로 붙어있는 무리의 갯수를 출력하는 문제이다.

 

DFS와 BFS 모두 가능하지만, DFS가 편해서 stack과 재귀를 사용한다.

풀이 순서는 다음과 같다.

 

1. N과 Map을 읽어온다.

2. N x N을 탐색하며 Map이 1일 때와 탐색 여부를 검사한다.

3. 위를 만족한다면 탐색 체크와 DFS를 진행한다.

4. DFS에서는 x와 y 방향으로 진행시키며 Map이 1일 때, DFS를 재귀시킨다.

5. 최종 depth를 stack에 저장 후, stack의 길이와 sort시킨 stack을 출력한다.

 

[C++]

#include <cstdio> 
#include <algorithm> // sort
#include <cstring> // memset
#include <deque> // stack
using namespace std;
int n = 0;
int map[26][26];
bool visited[26][26];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
deque<int> stk;


int solve_dfs(int depth, int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = 0, ny = 0;
		nx = x + dx[i];
		ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
			if (map[nx][ny] == 1 && !visited[nx][ny]) {
				visited[nx][ny] = 1;
				depth = solve_dfs(depth+1, nx, ny);
			}
		}
	}
	return depth;
}

int main() {
	scanf("%d", &n);
	memset(map, 0, sizeof(map));
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				visited[i][j] = 1;
				stk.push_back(solve_dfs(1, i, j));
			}
		}
	}
	sort(stk.begin(), stk.end());
	printf("%d\n", stk.size());
	for (int i = 0; i < stk.size(); i++) {
		printf("%d\n", stk[i]);
	}
	return 0;
}

 

[Python]

import sys
N = int(sys.stdin.readline())
M = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
stack = []

def solve_dfs(depth, x, y):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if M[nx][ny] == '1' and not visited[nx][ny]:
                visited[nx][ny] = True
                depth = solve_dfs(depth+1, nx, ny)
    return depth

for i in range(N):
    for j in range(N):
        if M[i][j] == '1' and not visited[i][j]:
            visited[i][j] = True
            stack.append(solve_dfs(1, i, j))

stack.sort()
print(len(stack))
for i in stack:
    print(i)