유기농 배추

풀이

 이 문제는 DFS, BFS 모두로 풀 수 있다. 나는 DFS로 문제를 풀었다. 2차원 그래프가 주어질 때 1로 연결된 덩어리의 개수(result)를 구하는 문제다.

1. result = 0 초기화
2. a*b 크기인 행렬을 이중 반복문을 돌린다.
   2.1. 만약 해당 그래프의 원소가 0이면 continue
   2.2. 만약 해당 그래프의 원소가 1이면 값을 0으로 바꾸고 주변 탐색(0으로 초기화), result++
3. result 반환

이 문제도 그렇게 어렵지는 않았지만, x, y축 거꾸로 되어 있어서 살짝 헷갈렸다..

시간 복잡도 : O(TMN)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.*;

public class Main {
    static int M,N;
    static int[][] graph;
    static int[] dx = new int[]{0, 0, 1, -1};
    static int[] dy = new int[]{1, -1, 0 ,0};
    public static void DFS(int x, int y) {
        graph[x][y] = 0;
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx && nx<N && 0<=ny && ny<M){
                if(graph[nx][ny]==1){
                    graph[nx][ny] = 0;
                    DFS(nx, ny);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int result = 0;
            graph = new int[N][M];
            for(int j=0; j<K; j++){
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st2.nextToken());
                int x = Integer.parseInt(st2.nextToken());
                graph[x][y] = 1;
            }

            for(int j=0; j<N; j++){
                for(int k=0; k<M; k++){
                    if(graph[j][k]==1){
                        DFS(j, k);
                        result++;
                    }
                }
            }
            bw.write(String.valueOf(result +"\n"));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

import sys
sys.setrecursionlimit(10000)
n = int(input())
result = []
def dfs(y, x):
    if graph[y][x] == 1:
        graph[y][x] = 0
        # 주변 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= a or ny < 0 or ny >= b:
                continue
            dfs(ny, nx)
        return True
    return False

for q in range(n):
    # 세팅 작업
    a, b, c = map(int, input().split())
    graph = [[0 for _ in range(a)] for _ in range(b)]
    for i in range(c):
        x, y = map(int, input().split())
        graph[y][x] = 1

    # 동 서 남 북
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    count = 0
    for i in range(a):
        for j in range(b):
            if dfs(j, i) == True:
                count += 1
    result.append(count)
for i in result:
    print(i)