[백준]1012. 유기농 배추 (java, python)

링크

유기농 배추

문제 분석

• 컴포넌트의 개수를 구하는 문제입니다
• bfs 또는 dfs를 돌며 모든 1을 탐색합니다
• 탐색 알고리즘을 실행한 횟수가 답이 됩니다

코드

JAVA

import java.util.*;

public class Q1012 {
    static int N, M, K;
    static boolean[][] map;
    static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        while(tc-- > 0) {
            M = sc.nextInt();
            N = sc.nextInt();
            K = sc.nextInt();
            map = new boolean[N][M];
            int ret = 0;

            for(int i = 0; i < K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                map[y][x] = true;
            }

            for(int y = 0; y < N; y++)
                for(int x = 0; x < M; x++)
                    if(map[y][x]) {
                        bfs(y, x);
                        ret++;
                    }
            System.out.println(ret);
        }
    }

    public static void bfs(int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{y, x});
        map[y][x] = false;

        while(!q.isEmpty()) {
            int[] cur = q.poll();

            for(int d = 0; d < 4; d++) {
                int ny = cur[0] + dy[d];
                int nx = cur[1] + dx[d];
                if(ny >= 0 && nx >= 0 && ny < N && nx < M && map[ny][nx]) {
                    q.add(new int[]{ny, nx});
                    map[ny][nx] = false;
                }
            }
        }
    }
}

PYTHON

import sys
read = sys.stdin.readline
getarr = lambda: map(int, read().split())


def bfs(y, x):
    q = [(y, x)]
    while q:
        y, x = q.pop()
        board[y][x] = 0
        for ny, nx in [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]:
            if 0 <= ny < N and 0 <= nx < M and board[ny][nx]:
                q += [(ny, nx)]


for _ in range(int(read())):
    M, N, K = getarr()
    board = [[0] * M for _ in range(N)]
    ret = 0
    for _ in range(K):
        v, w = getarr()
        board[w][v] = 1

    for i in range(N):
        while any(board[i]):
            bfs(i, board[i].index(1))
            ret += 1
    print(ret)