BOJ 2667 · 단지번호붙이기

알고리즘 분류 : DFS, BFS  

DFS/BFS 완전 탐색을 하여 풀 수 있는 문제다. 연결 그래프의 개수를 세는 문제와 비슷하다.

• 단지는 서로 이어져있으므로, 인접한 집(1)이 있는지 DFS로 탐색한다.
• DFS로 탐색하면서 집의 수를 센 후, 값을 0으로 변경한다.
• 0은 집이 없거나, 이미 방문한 곳이므로 다시 방문하지 않는다.
• DFS 탐색이 끝나면, 단지(인접한 집의 그룹)는 모두 0이 되어 있다.
• N x N 지도를 처음부터 끝까지 탐색하면서 아직 방문하지 않은 곳이 있다면, DFS로 다시 탐색한다.
• DFS를 처음 시작한 횟수가, 단지의 수이다.
• 각 단지내 집의 수를 오름차 순으로 정렬해야 하므로, 이를 저장하는 배열을 따로 만들고 정렬하여 출력한다.

---

C++ 소스코드 (DFS)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, cnt;
int a[25][25];
vector<int> apt;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    a[x][y] = 0;
    cnt++;
    for (int i=0; i<4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (!a[nx][ny]) continue;
        dfs(nx, ny);
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j]) {
                cnt = 0;
                dfs(i, j);
                apt.push_back(cnt);
            }
        }
    }
    sort(apt.begin(), apt.end());
    int len = apt.size();
    printf("%d\n", len);
    for (int i=0; i<len; i++) {
        printf("%d\n", apt[i]);
    }

    return 0;
}

✓ BFS 구현도 가능하다. 방법은 DFS와 동일하다.

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n;
int a[25][25];
vector<int> apt;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs(int i, int j) {
    queue<pair<int,int>> q;
    q.push(make_pair(i, j));
    a[i][j] = 0;
    int cnt = 1;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i=0; i<4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (!a[nx][ny]) continue;
            a[nx][ny] = 0;
            cnt++;
            q.push(make_pair(nx, ny));
        }
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j]) {
                apt.push_back(bfs(i, j));
            }
        }
    }
    sort(apt.begin(), apt.end());
    int len = apt.size();
    printf("%d\n", len);
    for (int i=0; i<len; i++) {
        printf("%d\n", apt[i]);
    }
    return 0;
}

---

Python 3 소스코드

import sys

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(sys.stdin.readline())
a = [list(sys.stdin.readline()) for _ in range(n)]
cnt = 0
apt = []


def dfs(x, y):
    global cnt
    a[x][y] = '0'
    cnt += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        if a[nx][ny] == '1':
            dfs(nx, ny)


for i in range(n):
    for j in range(n):
        if a[i][j] == '1':
            cnt = 0
            dfs(i, j)
            apt.append(cnt)

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

import sys
from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(sys.stdin.readline())
a = [list(sys.stdin.readline()) for _ in range(n)]
apt = []

def bfs(i, j):
    q = deque()
    q.append((i, j))
    a[i][j] = '0'
    cnt = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if a[nx][ny] == '1':
                a[nx][ny] = '0'
                cnt += 1
                q.append((nx, ny))
    return cnt

for i in range(n):
    for j in range(n):
        if a[i][j] == '1':
            apt.append(bfs(i, j))

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

---

참고

• 백준 온라인 저지 : BOJ 2667
• 연결 요소의 개수