[Baekjoon]백준 1012 유기농 배추(실버 2) - Python/C/C++

문제설명

예제

문제를 살펴보면 이전 문제(2667)는 총 몇개가 붙어있고, 붙어있는게 몇 묶음인지 물어보았다면

이번에는 입력 자체도 여러번 가능하며 총 몇 묶음인지 확인하는 문제이다

따라서, 이전 문제에서 사용한 dfs 함수에서 count 변수를 제거하여 dfs를 구현해야한다

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

def dfs(x, y):
    if x < 0 or x >= width or y < 0 or y >= length:
        return
    if field[y][x] == 1:
        field[y][x] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)

해당 함수를 사용하기에 있어 주의할 점이 존재한다

문제를 읽어보면 가로, 세로, 배추가 있는 위치를 입력받게 되는데 그렇게 된다면

평소 배열의 index와 조금 다르게 형성이 된다 일반적으로 가로와 세로로 index를 계산하지만

배열(리스트)의 경우에는 [세로index][가로index]가 되기 때문에 인자전달, 값 할당할 때 유의해야한다

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def dfs(x, y):
    if x < 0 or x >= width or y < 0 or y >= length:
        return
    if field[y][x] == 1:
        field[y][x] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)

num = int(input())
while num:
    width, length, cab_num = map(int, input().split())
    field = [[0 for _ in range(width)] for _ in range(length)]
    for _ in range(cab_num):
        index_x, index_y = map(int, input().split())
        field[index_y][index_x] = 1
    count = 0
    for i in range(length):
        for j in range(width):
            if field[i][j] == 1:
                dfs(j, i)
                count += 1
    print(count)
    num -= 1

해당 코드를 살펴보면 index_y, index_x가 서로 바뀌어 들어가고 있으며 dfs할 때에 가로, 세로로 인자를

전달하였기 때문에 dfs함수에서도 field[y][x]로 해당 위치에 1의 존재 유무를 확인하고 있다

또한, 재귀 호출의 최대 깊이를 설정해주어야 백준 제출시에 오류가 발생하지 않는다

마지막으로, C/C++ 연습을 위해 해당 코드를 그대로 재작성해보았다

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 50

int field[MAX_SIZE][MAX_SIZE];
int width, length;

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

void dfs(int x, int y) {
    if (x < 0 || x >= width || y < 0 || y >= length) {
        return;
    }

    if (field[y][x] == 1) {
        field[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(nx, ny);
        }
    }
}

int main() {
    int num;
    scanf("%d", &num);

    while (num--) {
        int cab_num;
        scanf("%d %d %d", &width, &length, &cab_num);

        memset(field, 0, sizeof(field)); // 0으로 초기화

        for (int i = 0; i < cab_num; i++) {
            int index_x, index_y;
            scanf("%d %d", &index_x, &index_y);
            field[index_y][index_x] = 1;
        }

        int count = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < width; j++) {
                if (field[i][j] == 1) {
                    dfs(j, i);
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

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

void dfs(int x, int y, vector<vector<int>>& field) {
    int width = field[0].size();
    int length = field.size();

    if(x < 0 || x >= width || y < 0 || y >= length) {
        return;
    }

    if(field[y][x] == 1) {
        field[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(nx, ny, field);
        }
    }
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num;
    cin >> num;

    while(num--) {
        int width, length, cab_num;
        cin >> width >> length >> cab_num;

        vector<vector<int>> field(length, vector<int>(width, 0));

        for(int i = 0; i < cab_num; i++) {
            int index_x, index_y;
            cin >> index_x >> index_y;
            field[index_y][index_x] = 1;
        }

        int count = 0;
        for(int i = 0; i < length; i++) {
            for(int j = 0; j < width; j++) {
                if(field[i][j] == 1) {
                    dfs(j, i, field);
                    count++;
                }
            }
        }
        cout << count << endl;
    }

    return 0;
}

분명 어색한 부분도 존재하겠지만, 최대한 빨리 익숙해져야겠다