[Python/Java] 백준1012번. 유기농 배추

 

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

1012번: 유기농 배추

 

문제 설명

해충 방지에 효과적인 배추흰지렁이를 구입하기로 한다.

이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.

어떤 배추에 배추흰지렁이가 한마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있다.

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우 인접해 있는 것이다.

0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

배추흰지렁이 마리 수를 출력한다.

 

풀이

• 입력받은 배추밭의 가로길이 M과 세로길이 N -> 2차원 배열로 구성
• 배추가 심어져 있는 위치의 개수 K -> K개의 좌표점은 1로 입력받고 나머지 좌표는 0으로 구성한다.
• 해당 좌표점이 1이면 DFS를 이용하여 상하좌우가 1인지 살펴보며 1인경우 0으로 값을 바꾼다.
  • 이때 상하좌우의 좌표점은 0이상 가로길이 M 세로길이 N 이하여야 한다. ( 좌표상을 벗어나서는 안된다는 뜻 )
• 이 dfs 함수가 끝나면 해당 좌표의 상하좌우 탐색이 끝났기 때문에 벌레 갯수를 하나 더해준다.

---

Python

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

t = int(input())

def dfs(x, y):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
	
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 이때 상하좌우의 좌표점은 0이상 가로길이 M 세로길이 N 이하여야 한다. ( 좌표상을 벗어나서는 안된다는 뜻 )
        if (0 <= nx < m) and (0 <= ny < n):
            if graph[ny][nx] == 1:
            	# 해당 좌표점이 1이면 DFS를 이용하여 상하좌우가 1인지 살펴보며 1인경우 0으로 값을 바꾼다.
                graph[ny][nx] = 0
                dfs(nx, ny)

for _ in range(t):
    m, n, k = map(int, input().split()) # m 가로 / n 세로
    # 배추가 심어져 있는 위치의 개수 K -> K개의 좌표점은 1로 입력받고 나머지 좌표는 0으로 구성한다.
    graph = [[0 for _ in range(m)] for _ in range(n)]
    cnt = 0
    
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1
    for x in range(m):
        for y in range(n):
            if graph[y][x] == 1:
                dfs(x, y)
                cnt += 1
    print(cnt)

---

Java

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

// 1012번. 유기농 배추
public class Baekjoon_1012 {
    static int cnt;
    static int m,n,k;
    static int[][] graph;
    public static void dfs(int x, int y){
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if((0 <= nx && nx < m) && (0 <= ny && ny < n)){
                if(graph[ny][nx] == 1){
                    graph[ny][nx] = 0;
                    dfs(nx, ny);
                }
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine());
        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            graph = new int[n][m];
            cnt = 0;

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(bf.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                graph[y][x] = 1;
            }

            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    if(graph[y][x] == 1){
                        dfs(x, y);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
        
    }
}