[BOJ] 1012번: 유기농 배추

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

1012번: 유기농 배추

 

문제

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

난이도

실버 2

 

Sol 1

배추밭 배열을 처음부터 끝까지 돌면서 배추가 있는 곳을 만날 때마다 DFS 재귀함수를 돌려 인접한 배추가 존재하는 위치를 방문 배열에 체크하고, cnt++를 해준다. 배추밭 배열을 끝까지 돌았을 때 최종 cnt 값을 답으로 출력. 

해당 풀이에서는 배추밭 배열과 방문 배열을 따로 만들었다.

public class BOJ1012 {
    static int M, N, K; // 배추밭의 가로 길이, 세로 길이, 배추가 있는 위치의 개수
    static int[][] farm; // 배추밭 배열
    static boolean[][] isvisited; // 방문 여부를 체크하기 위한 배열
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int cnt; // 필요한 배추흰지렁이의 수

    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 token = new StringTokenizer(bf.readLine());
            M = Integer.parseInt(token.nextToken());
            N = Integer.parseInt(token.nextToken());
            K = Integer.parseInt(token.nextToken());

            farm = new int[M][N];
            isvisited = new boolean[M][N];
            cnt = 0;
            // 매 테스트 케이스마다 배추밭 배열, 방문 배열, cnt를 초기화해줘야 한다

            for(int j=0; j<K; j++){
                token = new StringTokenizer(bf.readLine());
                int x = Integer.parseInt(token.nextToken());
                int y = Integer.parseInt(token.nextToken());
                farm[x][y] = 1;
            }
            // input

            for(int x=0; x<M; x++){
                for(int y=0; y<N; y++){
                    if(farm[x][y] == 1 && !isvisited[x][y]){ // 배추가 위치해 있고 해당 위치를 방문하지 않았다면
                        search(x, y); // dfs 메소드를 돌려 (x, y)와 인접해 있는 모든 배추의 위치를 방문 배열에 체크한다.
                        cnt++; // 배추흰지렁이 카운트를 1 더해준다
                    }
                }
            }
            // operation

            System.out.println(cnt);
            // output
        }
    }

    static void search(int x, int y){
        isvisited[x][y] = true; // 해당 좌표를 방문했음을 체크한다

        for(int i=0; i<4; i++){ // 해당 좌표의 상하좌우 체크
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < M && ny >= 0 && ny < N){
                if(farm[nx][ny] == 1 && !isvisited[nx][ny]){
                    search(nx, ny); // 해당 좌표의 인접한 곳에 배추가 존재한다면 dfs 함수를 돌려 체크한다
                }
            }
        }
    }
}

 

Sol 2

위와 같은 풀이에서 방문 배열을 제거하고 배추밭 배열을 boolean 형식으로 만들어 방문 배열처럼 사용했다

public class B1012_유기농배추 {
    static int M, N, K; // 배추밭의 가로 길이, 세로 길이, 배추가 있는 위치의 개수
    static boolean[][] farm;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int cnt;

    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++) {
            cnt = 0;

            StringTokenizer token = new StringTokenizer(bf.readLine());
            M = Integer.parseInt(token.nextToken());
            N = Integer.parseInt(token.nextToken());
            K = Integer.parseInt(token.nextToken());

            farm = new boolean[M][N];
            for(int j=0; j<K; j++){
                token = new StringTokenizer(bf.readLine());
                int x = Integer.parseInt(token.nextToken());
                int y = Integer.parseInt(token.nextToken());
                farm[x][y] = true;
            }
            // input

            for(int x=0; x<M; x++){
                for(int y=0; y<N; y++){
                    if(farm[x][y] == true){
                        search(x, y);
                        cnt++;
                    }
                }
            }
            // operation

            System.out.println(cnt);
            // output
        }
    }

    static void search(int x, int y){
        farm[x][y] = false;

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

            if(nx >= 0 && nx < M && ny >= 0 && ny < N){
                if(farm[nx][ny] == true){
                    search(nx, ny);
                }
            }
        }
    }
}

 

😅

시간이나 메모리가 줄어드나 싶어서 방문 배열을 없애봤는데(Sol 2) 오히려 시간이 조금 늘었다.. 왜 그러지? 스터디원들은 시간은 그대로 나오고 메모리가 줄었다고 하는데.. 

아래쪽이 Sol 1, 위쪽이 Sol 2 코드로 돌린 결과!