[백준] dfs - 1012번 유기농 배추 (Java)

문제링크

1012번: 유기농 배추

 

접근한 방법

• dfs

 

---

풀이방법

 

이 문제는 DFS로 해결할 수 있다.
0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶어 묶음의 수를 세면된다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점 에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

(2021.05.10 - [알고리즘/DFS BFS] - [이.코.테] Chapter 05 DFS/BFS - 음료수 얼려먹기 (Java) 에서 발췌)

 

---

소스코드 작성 방법

• dfs 메소드를 선언
  • 배추가 심어져있을 때 (map 값이 1일 때)만 탐색 진행
  • map 값을 0으로 해줌으로써 방문 처리
  • dfs 메소드를메 매개변수값의 인덱스를 이용하여 상하좌우로 호출
  • 종료조건)
    • 범위를 벗어날 때
    • map 값이 0일 때
• 이중 반복문을 사용하여 map을 전체 탐색하는데, 배추가 심어져있을 때만 방문

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.StringTokenizer;

public class Q_1012_OrganicCabage_20210512 {
    public static int m,n;
    public static int[][] map;
    public static int solution(){
        int result = 0;
        // dfs 수행
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 배추가 심어져있을 때만 방문
                if(map[i][j] == 1){
                    dfs(i, j);
                    result ++;
                }
            }


        }
        return result;

    }

    public static void dfs(int row, int col){
        if(row < 0 || col < 0 || row >=n || col >=m) return;

        if(map[row][col] == 1){
            // 방문처리
            map[row][col] = 0;

            // 상, 하, 좌, 우 방문 처리
            dfs(row - 1, col);
            dfs(row + 1, col);
            dfs(row, col - 1);
            dfs(row, col + 1);
        }

    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        for (int testcase = 0; testcase < t; testcase++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            map = new int[n][m];

            for(int i=0 ; i<k ; i++) {
                st = new StringTokenizer(br.readLine());
                int col = Integer.parseInt(st.nextToken());
                int row = Integer.parseInt(st.nextToken());
                map[row][col] = 1;
            }

            // 메소드 호출
            System.out.println(solution());

        }

        br.close();
        bw.close();
    }
}