[백준1012/java] 유기농 배추

- 문제 링크 : https://www.acmicpc.net/problem/1012

- 알고리즘 분류 : dfs/bfs

 

나는 DFS로 풀었다. 

 

• input = 배추의 위치 좌표가 주어진 배열이 주어진다.
• output = 필요한 배추흰지렁이의 개수
• DFS 사용 ⇒ 한 방향으로 갈 수 있는 곳까지 계속 탐색하고, 막다른 곳에 들어가면 거기에서 다시 안으로 쭉 들어간다. 막다른 곳에 도달할 때마다 배추지렁이의 개수를 늘리면 될듯하다.

 

다 풀고나서 계속 25%에서 틀려서 디버깅해보니까 continue를 써야하는 시점에 break를 써놔서 상하좌우를 전부 체크하지 않고 반복문을 빠져나갔기 때문이었다;;; 너무 황당한 실수...

import java.util.*;

 class CabbageField {
    int count; //배추 개수
    int cabbageMap[][]; //배추 위치 좌표
    boolean visited[][]; 
    int width;
    int height;
    int result;
    
    private int dx[] = {1,-1,0,0};
    private int dy[] = {0,0,1,-1};
   
    
    public CabbageField(int w, int h, int c) {
        this.width = w;
        this.height = h;
        this.count = c;
        this.cabbageMap = new int[w][h];
        this.visited = new boolean[w][h];
    }   
 
    
    public void dfs(int x, int y) {
        this.visited[x][y] = true;
        checkAdjacent(x,y);
    }
    
    private void checkAdjacent(int x, int y) {
        //상하좌우 4군데 체크
        for(int i = 0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= width || nx < 0 || ny >= height || ny < 0) {
                continue;
            }
            
            //재귀
            if(visited[nx][ny] == false && cabbageMap[nx][ny] == 1) {
                dfs(nx, ny);
            }
        }
        
    }
}




public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int total = sc.nextInt(); // case 개수
        CabbageField[] cabbageFields = new CabbageField[total];
        for(int i = 0; i<total; i++) {
            cabbageFields[i] = new CabbageField(sc.nextInt(), sc.nextInt(), sc.nextInt());
            
            //배추 좌표 입력
            for(int j = 0; j<cabbageFields[i].count; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cabbageFields[i].cabbageMap[x][y] = 1;
            }
            
            for(int w = 0; w<cabbageFields[i].width; w++) {
                for(int h = 0; h<cabbageFields[i].height; h++) {
                    if(cabbageFields[i].cabbageMap[w][h] == 1 
                        && cabbageFields[i].visited[w][h] == false) {
                            cabbageFields[i].dfs(w,h);
                            cabbageFields[i].result++;
                        }
                }
            }
            
           
            System.out.println(cabbageFields[i].result);
            
        }
       
    }
}

 

추가적으로 찾아본 반례를 첨부하면 아래와 같다.

 

<배추밭 모양>

0000

0101

0111

1
4 3 5
1 1
3 1
1 2
2 2
3 2

answer : 1