백준 1012번 : 유기농 배추

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

1012번: 유기농 배추

BFS사용

public class Main {

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

        for(int test=0; test<T; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");

            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            int cabbage= Integer.parseInt(st.nextToken());

            int[][] arr = new int[row][col]; //문제에서 주어진 최대값
            boolean[][] visited = new boolean[row][col];

            for(int i=0; i<cabbage; i++) {
                st = new StringTokenizer(br.readLine()," ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[a][b] = 1;
            }
            //------------배추 위치 입력 끝------------

            int count =0; //필요한 배추벌레 수
            for(int i=0; i<row; i++) {

                //입력된 배추밭의 크기만큼 반복문 실행
                for(int j=0; j<col; j++) {

                    //배추가 심어져 있는지와 처음 방문하는지 확인
                    if(arr[i][j]==1 && visited[i][j]!=true) {

                        //배추가 심어져 있다면 해당위치에서 탐색 시작
                        bfs(i,j,visited, row, col, arr);

                        //해당위치에 배추벌레 + 1
                        count++; 
                    }
                }//end for j
            }//end for i

            System.out.println(count);

        }//end for Test

    }//end main

    //BFS메서드
    private static void bfs(int startX, int startY, boolean[][] visited, int row, int col, int[][] arr) {
        //BFS에서는 다음에 탐색할 위치를 Queue에 저장함
        Queue<int[]> que = new LinkedList<int[]>();

        //que에 미리 시작위치를 넣어주고, 방문여부도 체크해줌
        que.offer(new int[] {startX,startY});
        visited[startX][startY] = true;

        //배추의 상하좌우에 인접한 배추가 있는지 확인하기 위한 설정 좌표
        int[] nearX = {0,0,-1,1};
        int[] nearY = {1,-1,0,0};

        //que에 값이 있는동안 (다음 탐색할 위치가 있을 때 까지)
        while(!que.isEmpty()) {
            int[] location = que.poll();

            //상하좌우 4곳을 확인해야하기 때문에 4번의 반복문
            for(int i=0; i<4; i++) {
                int x = location[0]+nearX[i];
                int y = location[1]+nearY[i];

                //배추밭의 크기보다 작거나 큰지 확인
                if(x<0 || y<0 || x>=row || y>=col) {
                    continue;
                }

                //인접한 곳에 배추가 있고, 방문하지 않은 곳이라면 
                if(arr[x][y] == 1 && visited[x][y]!=true) {

                    //다음 탐색위치를 que에 저장 및 방문확인을 해준다.
                    que.offer(new int[] {x,y});
                    visited[x][y] = true;
                }
            }

        }


    }//end BFS
}

BFS를 사용해서 문제를 (다른 블로그를 참고해서)풀었다.

BFS/DFS를 이제 막 풀어보기 시작한 상태라서 다소 어려운 문제였다.

BFS/DFS문제를 좀 더 풀어보고 다시 한 번 풀어봐야겠다.

 

---

참고자료

https://lotuus.tistory.com/98