[소프티어] 장애물 인식 프로그램 dfs 자바 풀이 레벨2

[소프티어] 장애물 인식 프로그램 dfs 자바 풀이

 

 

 

 

반타작..?

 

 

 

 

dfs의 전형적인 문제

전체 코드에 주석부분을 참고하자.

import java.io.*;
import java.util.*;

public class Main {

    public static int wallCnt = 0;
    public static List<Integer> wallSum = new ArrayList<>();
    public static int m[][];
    public static int curSum;
    public static Integer n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = new int[n][n];
        
        for(int i=0; i<n; i++){
            String s = br.readLine();
            for(int j=0; j<n; j++){
                m[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
            }
            
            // System.out.println(b.charAt(index));
            // if((int)c >= 'a'){x = 1;}
            
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(m[i][j] == 1){ // 장애물 발견시
                    wallCnt++; // 장애물 한세트 1개 카운팅하고
                    curSum = 1; // 장해물 크기 합 초기화해주고
                    m[i][j] = 0; // 장애물 일부 허물고
                    dfs(m, i, j); // 깊이탐색 출발
                    wallSum.add(curSum); // 탐색 끝나면 장애물 크기 합 curSum 저장하고 정렬해서 출력하자
                }
            }
        }
        bw.write(wallCnt + "\n");
        Collections.sort(wallSum);
        for(int i=0; i<wallSum.size(); i++){
            bw.write(String.valueOf(wallSum.get(i)) + "\n");
        }
        
        // List<Integer> list = Arrays.asList(m2);
        // int dap = Collections.frequency(list, min);
        
        // bw.write(String.valueOf(dap));
        bw.close();
    }

    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, 1, 0, -1};
    
    public static void dfs(int[][] m, int i, int j){
        for(int k=0; k<4; k++){
            int nx = i + dx[k]; // 상하좌우로 움직여보고
            int ny = j + dy[k];
            if( nx>=0 && nx<n && ny>=0 && ny<n ){ // 사각형 안에 들어오면서
                if(m[nx][ny] == 1){ // 장애물이 또 나왔으면 또 탐색해주자
                    m[nx][ny] = 0; // 장애물 허물고
                    curSum++;
                    dfs(m, nx, ny);
                }
            }
        }
    }
}