[알고리즘 / 백준] 1012 - 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

문제는 위와 같으며, 밭의 모든 위치를 확인하여 배추가 심어져 있지만 방문한 적 없는 경우 dfs 로 방문한 뒤, 한번 dfs 가 끝나면 하나의 연결 요소가 끝난 것으로 판단하여 result 를 +1 하는 방식으로 전체 연결 요소의 개수를 구하면 됩니다.

 

파이썬 코드는 다음과 같습니다.

import sys
sys.setrecursionlimit(100000)  # 재귀 가능 범위 제한 해결


def dfs(now_x, now_y):
    visited[now_x][now_y] = True  # 현재 위치 방문 처리
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dx, dy in directions:
        next_x, next_y = now_x + dx, now_y + dy  # 연결된 위치 확인
        if next_x < 0 or next_x >= n or next_y < 0 or next_y >= m:  # 밭의 범위를 벗어나는 경우 패스
            continue
        if array[next_x][next_y] and not visited[next_x][next_y]:  # 범위 내에 있으면서 배추가 심어져 있는데 방문하지 않았다면
            dfs(next_x, next_y)  # 연결된 위치 방문


t = int(sys.stdin.readline())
for _ in range(t):
    n, m, k = map(int, sys.stdin.readline().split())
    array = [[0] * m for _ in range(n)]  # 배추 위치를 표시할 배열 (배추가 있으면 1, 없으면 0)
    visited = [[False] * m for _ in range(n)]  # 방문 결과 배열 (방문한적 있으면 True, 없으면 False)
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        array[x][y] = 1  # 배추가 심어진 위치 표시
    result = 0
    # 전체 밭을 모두 확인
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:  # 배추가 심어져 있는데 방문한 적이 없다면
                dfs(i, j)  # 연결된 지역 모두 방문하기
                result += 1

    print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static int[][] array;
    private static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int[] nmk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            array = new int[nmk[0]][nmk[1]];
            visited = new boolean[nmk[0]][nmk[1]];
            for (int j = 0; j < nmk[2]; j++) {
                int[] xy = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                array[xy[0]][xy[1]] = 1;
            }
            int result = 0;
            for (int n = 0; n < nmk[0]; n++) {
                for (int m = 0; m < nmk[1]; m++) {
                    if (array[n][m] == 1 && !visited[n][m]) {
                        dfs(n, m);
                        result += 1;
                    }
                }
            }

            System.out.println(result);
        }
    }

    private static void dfs(int now_x, int now_y) {
        visited[now_x][now_y] = true;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < directions.length; i++) {
            int next_x = now_x + directions[i][0];
            int next_y = now_y + directions[i][1];
            if (next_x < 0 || next_x >= array.length || next_y < 0 || next_y >= array[0].length) {
                continue;
            }
            if (array[next_x][next_y] == 1 && !visited[next_x][next_y]) {
                dfs(next_x, next_y);
            }
        }
    }
}