[백준] 1012번 : 유기농 배추[JAVA]

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

# 문제

 

# 접근방식

• DFS, BFS 모두 사용할 수 있다.
• 배추의 위치 2차원 배열인 arr와 방문을 체크하는 2차원 배열인 check를 이용한다.
• 배추가 드문드문 나기 때문에 arr를 모두 탐색하면서 1인 좌표를 찾아야한다.
• 1인 좌표를 찾으면 그 좌표의 상, 하, 좌, 우를 탐색하면서 1이고 방문하지 않은 좌표를 찾는다.이 부분을 DFS로 나타내면 된다,
• m과 n의 범위에서만 찾도록 해야한다.

 

# 소스코드

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

public class Main {
    static int[][] arr;
    static boolean[][] check;
    static int m, n, k, count;

    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());

            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            arr = new int[m][n];
            check = new boolean[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = 0;
                    check[i][j] = false;
                }
            }

            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                arr[x][y] = 1;
            }

            count = 0;
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!check[i][j] && arr[i][j] == 1) {
                        dfs(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    static void dfs(int x, int y) {
        check[x][y] = true;

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

            if(cx>=0 && cy>=0 && cx<m && cy<n){
                if(!check[cx][cy] && arr[cx][cy]==1){
                    dfs(cx, cy);
                }
            }
        }
    }
}

 

# 성능

 

#회고

6개월 전에도 틀렸던 문제이다. 

처음에는 n과 m의 순서를 바꿔서 틀렸고, 두번째는 count변수를 전역변수로 선언해주면서 초기화도 같이 해줘서 틀렸다.

count변수를 main( )에 포함시켜주니 맞았다.

 

전역변수.. 지역변수... 다 아는줄 알았는데 더 심오한 세계가 있나보다. 역시 JAVA공부는 끝이 없다..