백준 1012 유기농 배추 알고리즘 자바 JAVA

 

 

백준 1012 유기농 배추 알고리즘 자바 JAVA 문제

 

백준 1012 유기농 배추 문제는 DFS/BFS 알고리즘을 사용해서 풀어보는 문제다. 기존 문제와 다른 점은 주어진 배열이 정사각형이 아닌 직사각형이라는 점이다. 두개의 알고리즘으로 푸는게 정석이기 때문에 두개 방법 모두 적용해서 결과값을 비교해보기로 한다. 문제의 시간 제한은 1초, 메모리 제한은 512MB가 주어진다.

 

 

 

DFS/BFS 알고리즘 참고

백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘

 

 

백준 1012 풀이과정

먼저 주어진 좌표값들을 가지고 인접행렬을 생성한다. 지렁이가 서식할 수 있는 지역을 고르기 위해서는 1의 분포를 알아야 하기 때문이다. 인접행렬이 구해지면, 모든 밭을 순회하면서 1과 방문지점을 검색하게 되고, 1이 검색된 지점에서 DFS 혹은 BFS 알고리즘으로 면적을 검색하게 된다.

 

내가 해맸던 곳은 좌표값을 지정하는 부분이다. 정사각형의 경우 N*N의 배열을 만들면 되는데, 직사각형은 x와 y좌표값을 각각 구분해서 코드를 짜야 하는 부분이 헷갈린다. 인접행렬에서의 X의 개념과 Array에서의 X개념이 헷갈리는 것이다. for문 순회는 Y좌표 부터 들어가는게 맞고, Array는 [Y][X] 순으로, 매개변수를 던질 때는 funtion(int X, int Y)순으로 정리하면서 코드를 작성한다.

 

 

 

 

 

알고리즘을 푸는 순서도는 다음과 같다.

1. 인접행렬을 구한다
2. DFS 알고리즘을 구현한다(스택+재귀함수 자료구조 사용)
3. BFS 알고리즘을 구현한다(큐 자료구조 이용)
4. 좌표값을 구하는 2D 문제에서는 Point 클래스를 사용한다.
5. ArrayList에 면적의값을 계산해서 새로운 요소로 추가한다.
6. StringBuilder을 사용해서 한번에 출력하기로 한다.

 

 

 

JAVA CODE + DFS/BFS

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.awt.Point;

public class A_1012 {
    public static int[][] matrix;
    public static int N,X,Y,COUNT;
    public static boolean[][] visit;
    public static int numOfBugs=0;
    public static int[] new_x = {1, -1, 0, 0};
    public static int[] new_y = {0, 0, -1, 1};
    public static ArrayList<Integer> total = new ArrayList<Integer>();
    public static Queue<Point> queue;
    


    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args){
        // 1. 인접행렬 만들기
        // 2. DFS 알고리즘 구현
        // 3. BFS 알고리즘 구현
        Scanner in = new Scanner(System.in);
        N = in.nextInt();


        for(int k=0; k<N; k++){
            X = in.nextInt();
            Y = in.nextInt();
            matrix = new int[50][50];
            visit = new boolean[50][50];
            int COUNT = in.nextInt();
            


            for(int i=0; i<COUNT; i++){
                int a = in.nextInt();
                int b = in.nextInt();
                matrix[b][a] = 1;
            }
            for(int i=0; i<Y; i++){
                for(int j=0; j<X; j++){
                    // System.out.print(matrix[0][1]);
                    if(matrix[i][j]==1 && !visit[i][j]){
                        numOfBugs=1;
                        // dfs(j,i)
                        // bfs(j,i);
                        total.add(numOfBugs);
                    }
                }
            }
            sb.append(total.size()+"\n");
            total.clear();
        }
        System.out.println(sb);
        
    }
    // BFS
    public static void bfs(int x, int y){
        queue = new LinkedList<>();
        queue.add(new Point(x,y));
        visit[y][x] = true;


        while(!queue.isEmpty()){
            Point temp = queue.poll();


            for(int i=0; i<4; i++){
                int NEW_X = temp.x+new_x[i];
                int NEW_Y = temp.y+new_y[i];    
                    // System.out.print(matrix[i][j]);
                    if(NEW_X>=0 && NEW_Y >=0 && NEW_X<X && NEW_Y<Y){
                        if(matrix[NEW_Y][NEW_X]==1 && !visit[NEW_Y][NEW_X]){                    
                            queue.add(new Point(NEW_X,NEW_Y));
                            visit[NEW_Y][NEW_X]=true;
                            numOfBugs++;
                        }
                    }
            }
        }
            
        
    }

    // DFS
    public static void dfs(int x, int y){
        visit[y][x] = true;

        for(int i=0; i<4; i++){
            int NEW_X = x+new_x[i];
            int NEW_Y = y+new_y[i];    
                // System.out.print(matrix[i][j]);
                if(NEW_X>=0 && NEW_Y >=0 && NEW_X<X && NEW_Y<Y){
                    if(matrix[NEW_Y][NEW_X]==1 && !visit[NEW_Y][NEW_X]){                    
                        dfs(NEW_X,NEW_Y);
                        numOfBugs++;
                    }
                }
        }
    }
}

 

 

백준 1012 유기농 배추 자바 결과값

 

결과를 확인해보면 입력값이 그리 깊은 노드가 아니기 때문에, 제한시간 1초 안에 문제가 해결된다. DFS 알고리즘은 400ms, 31MB가 소요되었고,  BFS 알고리즘의 경우 420ms, 32MB가 소요되었다. 얕은 노드에서 재귀와 스택을 활용한 DFS 알고리즘이 더 효율적인 것으로 보인다.