[백준 1012번] 유기농 배추 (Java 풀이)

백준알고리즘 1012번 : 유기농 배추 (Solved.ac 난이도 Silver2)

 

↑클릭시 문제 link로 이동합니다.😊

 

DFS의 기본이 되는 문제라고 볼수있겠다.
나는 기본이 없었던 것 같다.(...)
3년전에 풀었던 문제도 이렇게 헤매다보니 역시 알고리즘은 꾸준히 해야한다는 것을 깨닫는다.

복잡한 DFS 문제와는 다르게 1, 즉 배추가 있는 곳만 잘 찾아서 근처 상하좌우로 탐색을 하면서
'추가로 인접한 배추가 있는가?' 라는 것만 check하여 0으로 바꿔주면 된다.

따라서 탐색이 몇번 이루어졌는지 알필요가 없다는 점에서 깊이 우선 탐색 문제 중 간단한 편에 속한다고 생각한다.

 

 

풀이 과정

---

1. 배추밭을 2차원 배열로 정의하고, 배추가 있는 곳마다 값을 1로 대입한다.
2. 2중 for문으로 배추가 있는 곳을 찾고, dfs 메소드를 이용하여 상하좌우에 또 다른 배추가 있는지 탐색한다.
3. 탐색된 모든 곳은 0으로 바꿔주어 다시 탐색하지 않도록 하며 배추흰지렁이 마리수를 count한다.

 

 

 

소스 ▽

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

public class Main {// No1012 : 유기농 배추
static int farm[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            String[] base = br.readLine().split(" ");
            int x = Integer.parseInt(base[0]);
            int y = Integer.parseInt(base[1]);
            int baeChoo = Integer.parseInt(base[2]);
            int ans = 0;
            farm = new int[x][y];

            for (int j = 0; j < x; j++) {
                for (int k = 0; k < y; k++) {
                    farm[j][k] = 0;
                }
            }

            int tmp1;
            int tmp2;
            for (int j = 0; j < baeChoo; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                tmp1 = Integer.parseInt(st.nextToken());
                tmp2 = Integer.parseInt(st.nextToken());
                farm[tmp1][tmp2] = 1;
            }
            for (int j = 0; j < x; j++) {
                for (int k = 0; k < y; k++) {
                    if (farm[j][k] == 1) {
                        ans++;
                        dfs(j, k);
                    }
                }
            }
            System.out.println(ans);
        }
    }

    public static void dfs(int x, int y) {
        farm[x][y] = 0;
        if (x - 1 >= 0 && farm[x - 1][y] == 1) {dfs(x - 1, y);};
        if (y - 1 >= 0 && farm[x][y - 1] == 1) {dfs(x, y - 1);}
        if (x + 1 <= farm.length - 1 && farm[x + 1][y] == 1) {dfs(x + 1, y);}
        if (y + 1 <= farm[0].length - 1 && farm[x][y + 1] == 1) {dfs(x, y + 1);}
    }
}