[백준] 1012 - 유기농 배추

🖥️ 시작하며

def dfs(x, y):
    # 밭의 범위를 벗어나거나 배추가 없는 곳이면 종료
    if x < 0 or x >= N or y < 0 or y >= M or cabbage[x][y] == 0:
        return

    # 방문 처리
    cabbage[x][y] = 0

    # 인접한 배추 탐색
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)

def bfs(x, y):
    queue = deque([(x, y)])
    cabbage[x][y] = 0  # 방문 처리

    while queue:
        x, y = queue.popleft()

        # 방향 확인
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy

            # 밭의 범위 내이고 배추가 있는 곳이면 큐에 추가
            if 0 <= nx < N and 0 <= ny < M and cabbage[nx][ny] == 1:
                queue.append((nx, ny))
                cabbage[nx][ny] = 0  # 방문 처리

⚙️ 코드

# 1012. DFS

import sys

sys.setrecursionlimit(10000)
input = sys.stdin.readline


def dfs(x, y):
    # 밭의 범위를 벗어나거나 배추가 없는 곳이면 종료
    if x < 0 or x >= N or y < 0 or y >= M or cabbage[x][y] == 0:
        return

    # 방문 처리
    cabbage[x][y] = 0

    # 인접한 배추 탐색
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        # 가로길이, 세로길이, 배추가 심어진 위치 개수
        M, N, K = map(int, input().split())
        cabbage = [[0 for _ in range(M)] for _ in range(N)]

        for _ in range(K):
            X, Y = map(int, input().split())
            cabbage[Y][X] = 1

        count = 0
        for i in range(N):
            for j in range(M):
                if cabbage[i][j] == 1:
                    dfs(i, j)
                    count += 1

        print(count)

# 1012. BFS

from collections import deque
import sys

input = sys.stdin.readline


def bfs(x, y):
    queue = deque([(x, y)])
    cabbage[x][y] = 0  # 방문 처리

    while queue:
        x, y = queue.popleft()

        # 방향 확인
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy

            # 밭의 범위 내이고 배추가 있는 곳이면 큐에 추가
            if 0 <= nx < N and 0 <= ny < M and cabbage[nx][ny] == 1:
                queue.append((nx, ny))
                cabbage[nx][ny] = 0  # 방문 처리


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        # 가로길이, 세로길이, 배추가 심어진 위치 개수
        M, N, K = map(int, input().split())
        cabbage = [[0 for _ in range(M)] for _ in range(N)]

        for _ in range(K):
            X, Y = map(int, input().split())
            cabbage[Y][X] = 1

        count = 0
        for i in range(N):
            for j in range(M):
                if cabbage[i][j] == 1:
                    bfs(i, j)
                    count += 1

        print(count)

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

#define MAX 50

void dfs(int x, int y, int M, int N, int cabbage[MAX][MAX]) {
    if (x < 0 || x >= N || y < 0 || y >= M || cabbage[x][y] == 0)
        return;

    // 방문 처리
    cabbage[x][y] = 0;

    dfs(x - 1, y, M, N, cabbage);
    dfs(x + 1, y, M, N, cabbage);
    dfs(x, y - 1, M, N, cabbage);
    dfs(x, y + 1, M, N, cabbage);
}

int main() {
    int T, M, N, K;

    scanf("%d", &T);
    for (int t = 0; t < T; ++t) {
        scanf("%d %d %d", &M, &N, &K);

        int cabbage[MAX][MAX] = {0};

        for (int k = 0; k < K; ++k) {
            int x, y;
            scanf("%d %d", &x, &y);
            cabbage[y][x] = 1;
        }

        int count = 0;

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (cabbage[i][j] == 1) {
                    dfs(i, j, M, N, cabbage);
                    count++;
                }
            }
        }

        printf("%d\n", count);
    }
    return 0;
}

📌 소감