BOJ) 유기농 배추

유기농 배추

1012번: 유기농 배추

풀이

 

이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다.

그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ

 

총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다.

 

첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다.

하지만, group을 지어서 값을 변경하거나 이용하지 않기 때문에, 굳이 group을 저장하는 배열을 만들어야하는가 의구심이 들었다.

 

그래서, 두번째로 제출한 코드는 group 변수를 없애고, Map 자체에다가 group을 저장했다.

처음 map에 저장할 때, 배추가 있는 위치에 -1을 넣어주었다.

이 이유는, 배열을 초기화하면 모든 값이 0으로 초기화되는데, 두가지 고려사항이 있었다.

 

1번은 양배추 값을 1로 설정하게되면, group 인덱스를 2부터 시작해서 출력할 때 -1을 또 해줘야하는 사소한 귀찮음이 있었다.

2번은 Arrays.fill을 이용해서 -1로 초기화할까 하다가, 더 비효율적일 것 같아서 포기했다.

 

그래서 그냥 양배추에 -1을 집어 넣었고, 양배추가 있는 곳이면 -1을 황무지인 곳은 0을 map에 저장했다.

아무튼, 더 효율적이겠다고 생각했지만 결과는 그렇지 않았다.

 

코드 1

 

코드 2

왜인지는 모르겠지만 더 좋지 않다.. 흠...

 

두 코드 다 엄청 효율적이라는 느낌은 못받아서, 다른 사람들은 어떻게 풀었는지 봤다.

일단 가장 효율적으로 푼 분의 코드를 보니까 DFS로 코드를 짰다.

 

그래서 마지막으로 DFS로 바꿔서 코드를 짰는데, 서버 문제였는지 몰라도 크게 좋지는 않았다.

코드 3

 

이 문제에서는 grouping이 전부기 때문에, 딱히 어떤 부분을 기록해야할지 잘 모르겠다.

그래도 핵심 부분을 찝어보자면,

먼저, for문을 x,y 별로 돌리지 않고 0~n*m를 돌면서 x = i % m, y = i / m 으로 좌표를 저장한 점이 있다.

테스트 케이스에 따라서 여러번 입력을 받고 grouping을 하는 부분에도 반복이 들어가서, 여러 번 반복하는 것을 줄이기 위해서 썼다.

 

다음은 grouping 하는 방법이다.

맵을 돌면서 배추가 있는 부분에서 상하좌우 탐색을 하면서 group이 정해지지 않은 녀석들에게 group번호를 부여하고,

해당 위치로 들어가는 부분이다.

이 부분을 DFS 또는 BFS로 구현할 수 있는데, DFS는 해당 위치로 들어갈 때 재귀함수를 통해 들어가는 것이고, BFS는 LinkedList에 좌표를 저장해주면서 이동한다는 점이다. (이 문제에서는 DFS는 깊이를 우선 탐색하고 BFS는 너비를 우선 탐색한다 차이 정도.. group 좌표라 크게 차이 없다.)

 

 

코드 1

 

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

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    final static int CABBAGE = -1;

    private static class WORM {
        int x;
        int y;
        public WORM(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        int[] answer = new int[testCase];

        for(int i=0; i<testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            int map[][] = new int[n][m];
            for(int j=0; j<k; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x] = CABBAGE;
            }
            answer[i] = getWarms(m,n,map);
        }
        for(int ans : answer) {
            System.out.println(ans);
        }
        br.close();
    }

    private static int getWarms(int m, int n, int[][] map) {
        int groupIdx =0;
        LinkedList<WORM> moveList = new LinkedList<>();

        int mul = n*m;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;

            if(map[y][x] ==CABBAGE) {
                map[y][x] = ++groupIdx;
                moveList.offer(new WORM(x,y));

                while(!moveList.isEmpty()) {
                    WORM worm = moveList.poll();
                    for(int j=0; j<4; j++) {
                        int nx = worm.x+dx[j];
                        int ny = worm.y+dy[j];
                        if(inInArea(nx,ny,m,n)) {
                            if(map[ny][nx] == CABBAGE) {
                                map[ny][nx] =groupIdx;
                                moveList.offer(new WORM(nx,ny));
                            }
                        }
                    }
                }
            }
        }

        return groupIdx;
    }

    private static boolean inInArea(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n;
    }
}

 

코드 2

 

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

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    final static int CABBAGE = -1;

    private static class WORM {
        int x;
        int y;
        public WORM(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());

        for(int i=0; i<testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            int map[][] = new int[n][m];
            for(int j=0; j<k; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x] = CABBAGE;
            }
            System.out.println(getWarms(m,n,map));
        }
        br.close();
    }

    private static int getWarms(int m, int n, int[][] map) {
        int groupIdx =0;
        LinkedList<WORM> moveList = new LinkedList<>();

        int mul = n*m;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;

            if(map[y][x] ==CABBAGE) {
                map[y][x] = ++groupIdx;
                moveList.offer(new WORM(x,y));

                while(!moveList.isEmpty()) {
                    WORM worm = moveList.poll();
                    for(int j=0; j<4; j++) {
                        int nx = worm.x+dx[j];
                        int ny = worm.y+dy[j];
                        if(inInArea(nx,ny,m,n)) {
                            if(map[ny][nx] == CABBAGE) {
                                map[ny][nx] =groupIdx;
                                moveList.offer(new WORM(nx,ny));
                            }
                        }
                    }
                }
            }
        }

        return groupIdx;
    }

    private static boolean inInArea(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n;
    }
}

 

코드 3

 

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

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    final static int CABBAGE = 1;
    static int answer, map[][], m, n;

    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());

        for(int i=0; i<testCase; i++) {
            answer =0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            map = new int[n][m];

            for(int j=0; j<k; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x] = CABBAGE;
            }

            for(int y=0; y<n; y++) {
                for(int x=0; x<m; x++) {
                    if(map[y][x] == CABBAGE) {
                        answer++;
                        dfs(x,y);
                    }
                }
            }
            System.out.println(answer);
        }

        br.close();
    }

    private static void dfs(int x, int y) {
        map[y][x] =0;
        for(int i=0; i<4; i++) {
            int nx = x +dx[i];
            int ny = y +dy[i];
            if(isInArea(nx,ny,m,n)) {
                if(map[ny][nx] == CABBAGE) {
                    dfs(nx, ny);
                }
            }
        }
    }

    private static boolean isInArea(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n;
    }
}