[백준] 1012. 유기농 배추

---

문제

 

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

1012번: 유기농 배추

 

 전형적인 DFS(Depth-First Search) 문제다. 상하좌우로 인접한 1인 셀들은 배추흰지렁이가 모두 왕래할 수 있으므로 1개로 쳐야한다.

 

---

전략

 

01. DFS

 땅을 순회하면서 값이 1이고, 아직 방문하지 않은 땅을 발견한다면 그 지점부터 상하좌우를 확인해 주변의 땅 중 1이면서 아직 방문하지 않은 땅들을 재귀적으로 모두 방문처리한다. 이때 카운트를 1 올려주면 한 덩어리인 땅을 하나로 칠 수 있다.

 

---

풀이

 

Java

 

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

public class Main {
    static int[][] fields;
    static boolean[][] dfs;
    static int N, M, K;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) { // 테스트 케이스만큼 두 메서드를 실행
            baechuSetting(br);
            baechuRun();
        }
    }

    // 각 테스트 케이스마다 배추밭을 세팅하는 메서드
    private static void baechuSetting(BufferedReader br) throws IOException {
        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        M = info[0];
        N = info[1];
        K = info[2];
        fields = new int[N][M];
        dfs = new boolean[N][M];

        for (int i = 0; i < K; i++) {
            int[] point = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            fields[point[1]][point[0]] = 1;
        }
    }

    // 아직 방문하지 않은 땅을 순회하면서 찾는 메서드
    private static void baechuRun() {
        count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!dfs[i][j] && fields[i][j] == 1) {
                    baechuSearch(i, j);
                    count++;
                }
            }
        }

        System.out.println(count);
    }
    
    // 재귀적으로 인접한 땅이 1이면서 방문하지 않은 땅일 경우 해당 땅에서 실행되는 메서드
    private static void baechuSearch(int i, int j) {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        dfs[i][j] = true;

        for (int k = 0; k < 4; k++) {
            int x = j + dx[k];
            int y = i + dy[k];

            if (x >= 0 && x < M && y >= 0 && y < N) {
                if (!dfs[y][x] && fields[y][x] == 1) {
                    baechuSearch(y, x);
                }
            }
        }
    }
}

 

 위 풀이는 크게 4개의 메서드로 구성된다.

 

 main 메서드는 테스트 케이스 수를 받아 해당 수만큼 baechuSetting, baechuRun 메서드를 실행한다.

 

 baechuSetting 메서드는 배추밭의 가로길이 M, 세로길이 N, 배추 개수 K를 받아 클래스 멤버변수를 초기화하고, 배추밭도 함께 초기화한다.

 

 baechuRun 메서드는 이제 배추밭을 순회하면서 해당 땅이 1이면서 아직 방문하지 않은 땅을 찾아 baechuSearch 메서드를 실행시킨다. baechuSearch 메서드가 한번 실행되면 그 주변의 1이면서 아직 방문하지 않은 땅들이 모두 방문처리가 되므로 카운트를 1 올려주면 된다.

 

 baechuSearch 메서드는 DFS를 위한 재귀함수로 해당 땅 주변의 땅이 1이면서 아직 방문하지 않은 땅이라면 그 땅에 다시 baechuSearch 메서드를 재귀적으로 실행시키고 방문처리를 한다. 이 메서드를 통해 주변의 1인 땅들이 모두 재귀적으로 방문처리가 된다.

 

Python

 

import sys

sys.setrecursionlimit(10000)

class Baechu:
    def __init__(self, M, N, K):
        self.M = M
        self.N = N
        self.K = K
        self.fields = [[0 for _ in range(M)] for _ in range(N)]
        self.dfs = [[False for _ in range(M)] for _ in range(N)]

        self.setting()

    def setting(self):
        for _ in range(self.K):
            X, Y = map(int, sys.stdin.readline().split())
            self.fields[Y][X] = 1

    def run(self):
        count = 0

        for i in range(self.N):
            for j in range(self.M):
                if (not self.dfs[i][j] and self.fields[i][j] == 1):
                    self.dfs_func(j, i)
                    count += 1

        print(count)

    def dfs_func(self, j, i):
        dx = (-1, 1, 0, 0)
        dy = (0, 0, 1, -1)

        self.dfs[i][j] = True

        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if (0 <= x < self.N and 0 <= y < self.M and not self.dfs[x][y] and self.fields[x][y] == 1):
                self.dfs_func(y, x)


T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().rstrip().split())
    baechu = Baechu(M, N, K)
    baechu.run()

 

 

 파이썬도 마찬가지로 DFS로 풀었다. Baechu라는 클래스를 만들었고 이 안에서 모든 것들을 처리하게끔 했다. 입력값은 가장 아래에서 받아서 새로운 Baechu 객체를 만들어 넘겨주었다. Baechu클래스도 마찬가지로 네 개의 함수로 구성되어 있다.

 

 

Javascript (Nodejs)

 

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split(/\r?\n/);

let currentLine = 0;
function readLine() {
  return input[currentLine++];
}

let T = parseInt(readLine());
for (let t = 0; t < T; t++) {
  const [M, N, K] = readLine().split(" ").map(Number);
  const baechuField = Array.from({ length: N }, () => Array(M).fill(0));
  for (let k = 0; k < K; k++) {
    const [x, y] = readLine().split(" ").map(Number);
    baechuField[y][x] = 1;
  }

  let count = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (baechuField[i][j] === 1) {
        dfs(j, i, M, N, baechuField);
        count++;
      }
    }
  }

  console.log(count);
}

function dfs(x, y, M, N, baechuField) {
  if (x < 0 || x >= M || y < 0 || y >= N || baechuField[y][x] === 0) {
    return;
  }

  baechuField[y][x] = 0;

  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  for (let i = 0; i < 4; i++) {
    dfs(x + dx[i], y + dy[i], M, N, baechuField);
  }
}

 

 

 Nodejs의 경우에는 다음과 같이 풀었다. 똑같이 DFS를 사용하긴 했지만 별도의 클래스를 만드는 대신 dfs 함수 하나만으로 같은 역할을 하도록 했다. 살펴보아야 할 점은 Array.from() 메서드를 이용해 { length : N } 인 length속성을 가진 유사 배열을 생성한 뒤, 각각에 () => Array(M).fill(0) 를 적용해 2차원 배열을 만들었다는 것이다. 자바스크립트에서도 배열을 다음과 같이 쉽게 생성할 수 있다.