[백준 1012] 유기농 배추 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 52
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int arr[MAX_NUM][MAX_NUM];
int visited[MAX_NUM][MAX_NUM];
queue<pair<int, int>> q;

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

	int t;
	cin >> t;
	while (t--) {
		int m, n, k;
		cin >> m >> n >> k;

		while (k--) {
			int x, y;
			cin >> x >> y;
			arr[y][x] = 1;
		}

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1 && !visited[i][j]) {
					visited[i][j] = true;
					q.push({ i,j });
					cnt += 1;

					while (!q.empty()) {
						int x = q.front().first;
						int y = q.front().second;
						q.pop();

						for (int k = 0; k < 4; k++) {
							int nx = x + dx[k];
							int ny = y + dy[k];

							if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
							if (arr[nx][ny] == 0 || visited[nx][ny]) continue;

							visited[nx][ny] = true;
							q.push({ nx,ny });
						}
					}
				}
			}
		}

		cout << cnt << "\n";

		for (int i = 0; i < n; i++) {
			fill(arr[i], arr[i] + m, 0);
			fill(visited[i], visited[i] + m, false);
		}
	}

	return 0;
}

 

 

 

Python)

# 1012
import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

t = int(read().rstrip())

for _ in range(t):
    m, n, k = map(int, read().rstrip().split())

    arr = [ [0] * n for _ in range(m) ]
    visited = [ [False] * n for _ in range(m) ]

    for __ in range(k):
        x, y = map(int, read().rstrip().split())
        arr[x][y] = 1

    cnt = 0
    for i in range(m):
        for j in range(n):
            if arr[i][j] == 1 and not visited[i][j]:
                visited[i][j] = True
                q.append((i,j))
                cnt += 1

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

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if nx < 0 or nx >= m or ny < 0 or ny >= n:
                            continue
                        if arr[nx][ny] == 0 or visited[nx][ny]:
                            continue

                        visited[nx][ny] = True
                        q.append((nx,ny))



    print(cnt)