[BOJ Java] 1012 : 유기농 배추

급한 분들을 위한 반례 제안

 

1
2 3 5
0 0
1 0
1 1
0 2
1 2

 

답 : 1, 나올 수 있는 Output : 2

 

요약 : 처음 문제를 볼 때는, 최대 50 × 50 밭이라서, 한칸 한칸 비교하는 식으로 체크하는 로직을 만든다면 시간 복잡도 측면에서 충분히 해결할 수 있다고 생각했다. 하지만, 기존 로직에서 계속 오답 처리가 되었다. 나 스스로의 사고력에 갇혀서 반례를 찾지 못하는 것이라고 생각하여 질문 게시판을 보니, 모두 DFS 로 해결했다는 것을 알게 되었다. 

 

기존에는 DFS 는 Node 들을 만들어 해결하는 것이라고 생각했다. 하지만, 그렇게 하지 않더라도 큰 틀에서 DFS를 쓸 수 있다는 것을 이번에 확인한 시간이었다. 

 

 

단순히 어떻게 이런 "배추밭" 에서 DFS를 "잘 활용" 할 수 있는지는 아래에 설명하도록 하겠다.

 

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

1012번: 유기농 배추

시도 1.

먼저, 논리적으로 어떤 구조를 가지고 가는지 먼저 설명이 필요할 것이다.

아예 "배추들" 그룹(Set) 이 있으면 된다고 생각했다. 그리고 각 배추들 그룹을 묶어주는 커다란 그룹이 하나 존재하는 식이다.

이렇게 한다면, 만약 위에서부터 하나하나 검사하는 식으로 체크가 이루어진다. 

만약 기존 그룹들을 탐색하여, "인접" 하는 그룹이 나타난다면, 해당 그룹(Set) 에다가 그 배추를 집어넣는다. 

만약 "인접"해 있는 그룹이 존재하지 않는다면, 새로운 그룹(Set) 을 만들고, 그 그룹 첫번째 멤버로 해당 배추를 집어넣는 식으로 진행했다.

 

위의 로직을 활용한 Java Code

public class Q1012 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            calculate(br);
        }
    }
    static void calculate(BufferedReader br) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int xLength = Integer.parseInt(st.nextToken());
        int yLength = Integer.parseInt(st.nextToken());
        int cabbageCount = Integer.parseInt(st.nextToken());

        int[][] cabbageGround = makeGround(br,xLength,yLength,cabbageCount);
        System.out.println(countCabbageGroup(cabbageGround));
    }
    static int countCabbageGroup(int[][] ground){
        Set<Set<Cabbage>> cabbageSet = new HashSet<>(); // 큰 그룹(위의 검은색 원)

        for(int y = 0; y < ground.length; y++){
            for(int x = 0; x < ground[0].length; x++){
                if(ground[y][x] == 1){ // 배추가 존재한다면
                    Set<Cabbage> oneCabbageGroup = alreadyInSet(cabbageSet,y,x); // 인접해있는 그룹이 있는지 검사
                    if(oneCabbageGroup != null){ // 만약 그룹이 존재한다면? 
                        oneCabbageGroup.add(new Cabbage(x,y)); // 해당 작은 그룹에다가 배추를 더하기
                    }else{
                        Set<Cabbage> newSet = new HashSet<>(); // 인접 그룹이 없다면 새로운 그룹 만들기
                        newSet.add(new Cabbage(x,y));
                        cabbageSet.add(newSet); // 배추를 추가해 주고, 큰 그룹에 넣기
                    }
                }
            }
        }
        return cabbageSet.size(); // 큰 그룹 안에 몇 개의 작은 배추그룹이 있는지?
    }
    static Set<Cabbage> alreadyInSet(Set<Set<Cabbage>> cabbageSet, int y, int x){
        for(Set<Cabbage> oneSet : cabbageSet){ // Set 임을 감안하여, Enhanced For 문 사용
            for(Cabbage oneCabbage : oneSet){ // 큰 그룹 내 작은 그룹 찾기
                if(isInGroup(oneCabbage,y,x)){ // 인접한 것이 있다면, 해당 작은 그룹을 리턴하기
                    return oneSet;
                }
            }
        }
        return null; // 없다면, 일부러 null 값을 리턴하여, 인접하는 그룹이 없음을 알림.
    }
    static boolean isInGroup(Cabbage cabbage, int y, int x){ // 해당 그룹안에 인접해 있는지 체크하는 로직.
        if(cabbage.y == y){
            return Math.abs(cabbage.x - x) == 1; 
        }
        if(cabbage.x == x){
            return Math.abs(cabbage.y - y) == 1;
        } // 결국 상하좌우 안에 있어야 한다는 소리. 대각선은 해당되지 않는다!
        return false;
    }

}
class Cabbage{
    int x;
    int y;

    public Cabbage(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

이 코드의 반례 및 허점

 

반례

 

1
2 3 5
0 0
1 0
1 1
0 2
1 2

답 - 1, Output - 2

 

위의 반례는 아래와 같이 생겼다.

 

1 1

0 1

1 1

 

이 부분은 분명히 하나의 그룹으로 처리되어야 한다. 하지만, 순서대로 읽어나오다 보니, 위의 두줄, 중간 한줄 까지는 정상적으로 하나의 그룹으로써 인식되어 나오지만, 아래 줄 왼쪽 배추부터는 다른 그룹으로 인식되는 참사(?) 가 벌어지는 문제를 발견할 수 있었다.

 

그렇다면, 미리 대각 부분도 하나의 그룹으로써 처리하면 안되는가?

그렇게 처리했을 경우. 당장 아래의 대표예제 케이스에서 문제가 발생한다. 대각선으로 이어진 부분은 같은 그룹이 아니다!

 

로직 상, 미리 오른쪽을 인식하고 다시 왼쪽으로 가는, 그런 나 스스로만의 편의를 기대하고 프로그래밍 하기 힘들다는 판단을 내리고, 위의 코드를 모두 갈아치우기로 했다. 

 

시도 2. DFS 를 활용하여 문제 해결하기

처음에는 DFS 를 활용하여야 한다는 생각을 전혀 하지 못하고 있다가, 이때 많이 고민을 했다. 

 

기존의 DFS 를 활용하는 것은, Graph 가 존재하여야 했고, Node 를 하나하나 만들어서 어떻게 다른 Node 들과 이어주어야 할지 고민해야 했다. 그리고 어떻게 방문했는지 표기해 주는 것도 고려해야 할 대상 중 하나였다. 

 

어떻게 단순히 좌표평면 상에 0 과 1로만 이루어진 "배추밭" 에서, DFS를 활용할 지 곰곰히 생각해 주던 와중에 

 

"차라리 이미 체크된 배추를 사라지게 하면, 다시 재방문할 일이 없지 않을까?" 하는 아이디어가 떠오르게 된다.

 

핵심 로직

(0,0) 부터 순차적으로 밭을 탐색하는 것은 같다. 

전역 변수 cabbageGroupCount 를 0 으로 세팅하고, 배추가 존재하면 바로 DFS를 타는 로직으로 넘어간다.

 

맨 처음 상하좌우를 확인하기 전에, 해당 배추를 0으로 바꾼다. 그리고 나서 상하좌우를 for 문을 돌면서 확인한다. 

이렇게 해 주는 경우, 기존의 배추가 없는 식으로 나오기 때문에, 이미 방문한 배추를 재방문할 확률이 사라진다. 기존에 방문한 배추를 인식하지 못하기 때문이다. 

 

그렇게, DFS 를 통해 방문한 모든 배추 그룹을 한 방에 "뽑는다".(여기서 배추를 뽑는다는 말은, 선택하는 것이 아니라 뿌리뽑는다 와 동일한 말이다)

 

그렇게 한 방에 한 그룹을 DFS 를 통해서 "뽑아" 버리면, 중간에 재방문할 가능성을 완전히 지우는 셈이다. 

그리고 한번 DFS 를 거쳤으면, 한 "그룹"을 "뽑은" 것이기 때문에, cabbageGroupCount 를 하나 늘려 준다.

 

DFS 안의 로직에서는, 새로 이동할 x,y 좌표를 세팅해 준다. 왼쪽, 위, 오른쪽, 아래 순으로 이동하는 것으로 위에서 전역변수로 세팅해 주었다. 

 

그리고 밭 경계에서 벗어나 주는지 확인하고, 해당 방면에 배추가 존재하는지 확인한다. 

둘다 true 가 나오면 본인을 다시 부르면서 재귀적으로 동작한다. 

 

아래는 최종적으로 문제풀이에 성공한 자바 코드이다.

public class Q1012DFS {
    static int cabbageGroupCount;
    static List<List<Integer>> direct = List.of(List.of(-1,0),
                                                List.of(0,-1),
                                                List.of(1,0),
                                                List.of(0,1));
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            cabbageGroupCount = 0;
            calculate(br);
        }
    }
    static void calculate(BufferedReader br) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int xLength = Integer.parseInt(st.nextToken());
        int yLength = Integer.parseInt(st.nextToken());
        int cabbageCount = Integer.parseInt(st.nextToken());

        int[][] cabbageGround = makeGround(br,xLength,yLength,cabbageCount);
        searchGround(cabbageGround);
        System.out.println(cabbageGroupCount);
    }
    static void searchGround(int[][] cabbageGround){
        for(int y = 0; y < cabbageGround.length; y++){
            for(int x = 0; x < cabbageGround[0].length; x++){
                if(cabbageGround[y][x] == 1){
                    findByDFS(x,y,cabbageGround);
                    cabbageGroupCount++;
                }
            }
        }
    }
    static void findByDFS(int x, int y, int[][] cabbageGround){
 
        cabbageGround[y][x] = 0;
        for (List<Integer> direction : direct) {
            int moveY = y + direction.get(1);
            int moveX = x + direction.get(0);
            if (isInBound(moveX, moveY, cabbageGround) && cabbageGround[moveY][moveX] == 1) {
                findByDFS(moveX, moveY, cabbageGround);
            }
        }
    }
    static boolean isInBound(int x, int y, int[][] cabbageGround){
        return (0 <= y && y < cabbageGround.length) && (0 <= x && x < cabbageGround[0].length);
    }
}