백준 1012 번 : 유기농 배추 (java)

 

문제

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

1012번: 유기농 배추

 

난이도 : 실버 2

유형 : 그래프, BFS, DFS 

 

접근법

DFS, BFS 둘다 적용이 가능합니다. 배열의 4방향을 뜻하는 X, Y 변수를 두고 사방을 탐색하여 모든 1을 찾아면 됩니다.

다만, 상하좌우로 연결되어있는 것 끼리만 탐색을 한다는 조건이 있습니다.

 

 

따라서, 배열의 모든요소를 탐색하는 반복문에 BFS 탐색을 실시합니다.

한번의 탐색이 끝나면 count가 증가하고 탐색시에 visit배열로 방문 체크를하므로 다음 반복시 반복하지 않는 배열중 "1"인 값을찾아 해당 과정을 반복합니다.

 

 

풀이

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

public class BOJ1012 {
    static int[][] cabbage;
    static boolean[][] visit;
    static Queue<int[]> qu = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();
    static int[]  X = {1, 0, -1 ,0};
    static int[]  Y = {0, -1, 0, 1};
    static int N, M;

    // 1,0우 0,-1상 -1,0좌 0,1아래
    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 st1 = new StringTokenizer(bf.readLine());
            M = Integer.parseInt(st1.nextToken());//새로
            N = Integer.parseInt(st1.nextToken()); //가로
            int K = Integer.parseInt(st1.nextToken()); //배추 갯수
            cabbage = new int[M][N];
            visit = new boolean[M][N];
            int cnt=0;

            for(int j=0; j<K; j++){
                StringTokenizer st = new StringTokenizer(bf.readLine());
                cabbage[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]  = 1;
            }

            for (int row=0; row<M; row++){
                for (int col=0; col<N; col++){
                    if(cabbage[row][col] ==1 && !visit[row][col]){
                        visit[row][col] =  true;
                        bfs_bug(row, col);
                        cnt++;
                    }
                }
            }
            sb.append(cnt+ "\n");
        }
        System.out.println(sb.toString());
    }

    static void bfs_bug(int x_param, int y_param){
        qu.add(new int[] {x_param,y_param});

        while(!qu.isEmpty()){
            int[] qu_Val= qu.poll();
            for(int i=0; i<4; i++){
                int t_x = qu_Val[0] +X[i];
                int t_y = qu_Val[1] +Y[i];

                if(t_x > -1 && t_y > -1 && t_x <M && t_y < N)
                    if(cabbage[t_x][t_y] == 1 && !visit[t_x][t_y]){
                        qu.add(new int[] {t_x, t_y});
                        visit[t_x][t_y] = true;
                    }
            }
        }
    }

}