본문 바로가기

Programming/BOJ

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와 동일하다.

✓ BFS 소스 보기




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)


✓ BFS 소스 보기




참고



태그