[Baekjoon]백준 2667 단지번호붙이기(실버 1) - Python/C/C++

문제설명

문제를 살펴보면 지도가 주어지고, 해당 지도에서 연결된 단지를 찾아 출력하는 문제이다.

일단 위에서부터 지도를 확인하다가, 1을 발견하면 해당 위치로부터 연결된 모든 집을 탐색해야한다.

문제 해결을 위해 DFS를 사용하기로 하였으며, 사용 과정에 있어서 스캔이 완료되면

중복 검사의 가능성이 존재하므로 0으로 바꾸어주어야 중복 탐색을 막을 수 있다.

DFS를 사용하기위해 dx, dy 배열을 선언하여 방향을 설정해준다

이후 앞서 dfs 함수를 선언하고 탐색하였을때 1이 존재한다면 0으로 변환함과 동시에 count 변수에 값을 저장한다

import sys
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y):
    global count
    if x < 0 or x >= size or y < 0 or y >= size:
        return
    if Complex[x][y] == 1:
        count += 1
        Complex[x][y] = 0
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            dfs(xx, yy)

Complex = []
size = int(input())
for _ in range(size):
    Complex.append(list(map(int, input().strip())))
    
result = []
count = 0
for i in range(size):
    for j in range(size):
        if Complex[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0
            
result.sort()
print(len(result))
for k in result:
    print(k)

해당 코드를 그대로 C/C++로도 구현해보았다

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 25

int size;
int complexMap[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE] = {0};

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int count; 

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void dfs(int x, int y) {
    if (x < 0 || x >= size || y < 0 || y >= size) {
        return;
    }
    
    if (complexMap[x][y] == 0) {
        return;
    }
    
    complexMap[x][y] = 0;
    count++;
    
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        dfs(next_x, next_y);
    }
}

int main() {
    scanf("%d", &size);
    
    // 지도 정보 입력받기
    for (int i = 0; i < size; i++) {
        char row[MAX_SIZE];
        scanf("%s", row);
        for (int j = 0; j < size; j++) {
            complexMap[i][j] = row[j] - '0';
        }
    }
    
    int result[MAX_SIZE * MAX_SIZE];
    int complex_count = 0;
    
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (complexMap[i][j] == 1) {
                count = 0;
                dfs(i, j);
                result[complex_count++] = count;
            }
        }
    }
    
    qsort(result, complex_count, sizeof(int), compare);
    
    printf("%d\n", complex_count);
    for (int i = 0; i < complex_count; i++) {
        printf("%d\n", result[i]);
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int mapsize;
vector<vector<int>> complexMap;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int count_per_complex;

void dfs(int x, int y) {
    if (x < 0 || x >= mapsize || y < 0 || y >= mapsize) {
        return;
    }
    
    if (complexMap[x][y] == 0) {
        return;
    }
    
    complexMap[x][y] = 0;
    count_per_complex++;
    
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        dfs(next_x, next_y);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> mapsize;
    
    complexMap.resize(mapsize, vector<int>(mapsize));
    for (int i = 0; i < mapsize; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < mapsize; j++) {
            complexMap[i][j] = row[j] - '0';
        }
    }
    
    vector<int> result;
    
    for (int i = 0; i < mapsize; i++) {
        for (int j = 0; j < mapsize; j++) {
            if (complexMap[i][j] == 1) {
                count_per_complex = 0;
                dfs(i, j);
                result.push_back(count_per_complex);
            }
        }
    }
    
    sort(result.begin(), result.end());
    
    cout << result.size() << "\n";
    for (int count : result) {
        cout << count << "\n";
    }
    
    return 0;
}

너무 오랜만에 C/C++을 사용한 터라 AI의 도움을 조금 받았지만, 앞으로는 혼자 힘으로 작성해보도록 해보겠습니다

다른 활동 하느라 오랜만에 작성하게 되어 조금 어색하지만, 다시 꾸준히 나아가 보겠습니다