유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

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

public class Main {
    static int[] dx= {1, 0, -1, 0};
    static int[] dy= {0, 1, 0, -1};
    static int[][] arr;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        // 입력의 첫 줄에는 테스트 케이스의 개수 T
        int t = Integer.parseInt(br.readLine());
        // 배추밭의 가로길이 M(1 <= M M= 50), 세로길이 N(1 <= N <= 50), 배추가 심어져 있는 위치의 개수 K(1<= K <= 2500)
        while(t-- > 0) {
            int ans = 0;
            st = new StringTokenizer(br.readLine(), " ");
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            arr = new int[n][m];
            for(int i = 0; i < k; i ++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr[y][x] = 1;
            }

            for(int i = 0; i < n; i ++) {
                for(int j = 0; j < m; j ++) {
                    if(arr[i][j] == 1) {
                        dfs(i, j);
                        ans += 1;
                    }
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb);
    }

    public static void dfs(int y, int x) {
        arr[y][x] = 0;
        for(int i = 0; i < 4; i ++) {
            int zy = y + dy[i];
            int zx = x + dx[i];

            if(zy >= 0 && zy < arr.length && zx >= 0 && zx < arr[0].length) {
                if(arr[zy][zx] == 1) {
                    dfs(zy, zx);
                }
            }
        }
    }
}

# 입력의 첫 줄에는 테스트 케이스의 개수 T
t = int(input())

# 배추밭의 가로길이 M(1 <= M M= 50), 세로길이 N(1 <= N <= 50), 배추가 심어져 있는 위치의 개수 K(1<= K <= 2500)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(y, x, arr):
    arr[y][x] = 0
    for i in range(4):
        zy = y + dy[i]
        zx = x + dx[i]

        if 0 <= zy < len(arr) and 0 <= zx < len(arr[0]):
            if arr[zy][zx] == 1:
                dfs(zy, zx, arr)
    return True


while True:
    if t == 0:
        break
    # 로직
    ans = 0
    mnk = list(map(int, input().split(' ')))

    m = mnk[0]
    n = mnk[1]
    k = mnk[2]
    arr = [[0 for j in range(m)] for i in range(n)]
    for i in range(k):
        xy = list(map(int, input().split(' ')))
        x, y = xy[0], xy[1]
        arr[y][x] = 1

    for j in range(n):
        for i in range(m):
            if arr[j][i] == 1 and dfs(j, i, arr):
                ans += 1

    print(ans)
    # 로직
    t -= 1

• 자바로는 쉬웠던 문제였는데, 아직 파이썬 입출력 특히 2차원 배열 관련 부분에 대한 이해가 부족해서 시간이 좀 걸렸던거 같다.
• DFS로 접근하여 고립되어 있는 배추들의 모음을 찾아서 0으로 바꿔준다음. 답이 될 ans 변수에 1을 더해준다.
• 그렇게 해주면 비슷한 DFS 문제처럼 풀리게 된다.

 

• 나중에 공부할 것: 파이썬 입출력