유기농 배추

문제

유기농 배추
전형적인 플러드 필 문제입니다.

풀이

맨 왼쪽 위 부터 오른쪽 아래 까지 탐색한 적 없는 배추를 발견하면 DFS를 통해 그 배추와 연결된 모든 배추를 탐색합니다. DFS 탐색한 횟수가 답이 됩니다.

코드

Python

m: int
n: int
cabbages: set[tuple[int, int]]
visited: list[list[bool]]
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
 
def dfs(x: int, y: int):
    visited[x][y] = True
 
    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 (nx, ny) in cabbages and not visited[nx][ny]:
            dfs(nx, ny)
 
 
def solve():
    global m, n, cabbages, visited
 
    m, n, k = map(int, input().split())
    visited = [[False] * n for _ in range(m)]
    cabbages = set()
 
    for _ in range(k):
        x, y = map(int, input().split())
        cabbages.add((x, y))
 
    answer = 0
    for x in range(m):
        for y in range(n):
            if (x, y) in cabbages and not visited[x][y]:
                answer += 1
                dfs(x, y)
 
    print(answer)
 
 
for _ in range(int(input())):
    solve()

C++

#include <bits/stdc++.h>
using namespace std;
 
int m, n;
vector<vector<bool>> isCabbage;
vector<vector<bool>> visited;
 
array<int, 4> dx = {1, -1, 0, 0};
array<int, 4> dy = {0, 0, 1, -1};
 
void dfs(int x, int y) {
    visited[x][y] = true;
 
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
 
        if (nx < 0 or nx >= m or ny < 0 or ny >= n)
            continue;
 
        if (isCabbage[nx][ny] and not visited[nx][ny])
            dfs(nx, ny);
    }
}
 
void solve() {
    int k;
    cin >> m >> n >> k;
 
    isCabbage = visited = vector(m, vector(n, false));
 
    while (k--) {
        int x, y;
        cin >> x >> y;
        isCabbage[x][y] = true;
    }
 
    int answer = 0;
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < n; y++) {
            if (isCabbage[x][y] and not visited[x][y]) {
                answer++;
                dfs(x, y);
            }
        }
    }
 
    cout << answer << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--)
        solve();
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    static int m, n;
    static boolean isCabbage[][], visited[][];
 
    static final int[] dx = { 1, -1, 0, 0 };
    static final int[] dy = { 0, 0, 1, -1 };
 
    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++)
            solve();
 
        bw.close();
    }
 
    static void solve() throws IOException {
        StringTokenizer tk = new StringTokenizer(br.readLine());
        m = Integer.parseInt(tk.nextToken());
        n = Integer.parseInt(tk.nextToken());
        int k = Integer.parseInt(tk.nextToken());
 
        isCabbage = new boolean[m][n];
        visited = new boolean[m][n];
 
        for (int i = 0; i < k; i++) {
            tk = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(tk.nextToken()), y = Integer.parseInt(tk.nextToken());
            isCabbage[x][y] = true;
        }
 
        int answer = 0;
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (isCabbage[x][y] && !visited[x][y]) {
                    answer++;
                    dfs(x, y);
                }
            }
        }
 
        bw.write(answer + "\n");
    }
 
    static void dfs(int x, int y) {
        visited[x][y] = true;
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
 
            if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                continue;
 
            if (isCabbage[nx][ny] && !visited[nx][ny])
                dfs(nx, ny);
        }
    }
}