백준[자바]_1388_바닥장식_깊이우선탐색

오늘은 평소에 약했던 부분인 DFS탐색문제를 풀어보았다. 이번에는 단계별로 문제풀기에 분류되어 있지 않지만 학원사람들과 알고리즘 스터디를 하기 위해서  찾은 비교적 쉬운 DFS탐색 문제이다. 

[ 접근 ]

1. '-' 이 같은 행에 연결되어 있거나 '|'이 같은 열에 연결되어 있는 경우 하나의 나무 판자로 카운트 한다.
   1. 맵을 탐색하다가 해당 위치에 있는 나무판자의 모양이 '-'라면 좌우만 탐색, '|'라면 상하만 탐색한다. 
   2. 모든 위치에서 DFS탐색을 하되 재귀가 끝나는 위치에서 count해준다.
   3. 경우의 수가 두 가지 뿐이므로 조건의 편의성을 위해서 -와 |를 true, false로 변환해서 map에 저장했다.

 

비교적 쉬운 문제이기 때문에 나머지는 소스코드를 보면 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

package DFS;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _1388_바닥장식 {
    
    static boolean visit[][];
    static boolean   map[][];
    static int n,m;
    //                    상 하  좌 우
    static int dx[] = {-1, 1,  0, 0};
    static int dy[] = { 0, 0, -1, 1};
    static int count = 0;
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        visit = new boolean[n][m];
        map   = new boolean[n][m];
        
        for(int i=0; i<n; i++) {
            char c[] = br.readLine().toCharArray();
            for(int j=0; j<m; j++) {
                if(c[j] == '-') {
                    map[i][j] = true;
                }//|인경우는 기본값 false로 두기
            }
        }
        
        /*
         * for(boolean b[] : map) { for(boolean bb : b) { System.out.printf("%-5s", bb);
         * } System.out.println(); }
         */
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(!visit[i][j]) {
                    dfs(i,j);
                    count++;
                    
                }
            }
        }
        
        
        System.out.println(count);
    }
    private static void dfs(int x, int y) {
        // TODO Auto-generated method stub
        visit[x][y] = true;
        
        if(map[x][y]) {//'-'
            for(int i=2; i<4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                
                if(xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
                
                if(!visit[xx][yy]&& map[xx][yy] ) {
                    visit[xx][yy] = true;
                    dfs(xx,yy);
                }
            }
            
        }else {//'|'
            for(int i=0; i<2; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                
                if(xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
                
                if(!visit[xx][yy] && !map[xx][yy]) {
                    visit[xx][yy] = true;
                    dfs(xx,yy);
                }
            }
        }
    }
 
}
 
 
/*
    - 인 경우는 좌우만 탐색 
    | 인 경우는 상하만 탐색
*/