[Sofreer 문제풀이] Lv.2(장애물 인식 프로그램) feat. Java

 

1. 장애물 인식 프로그램

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

public class Main {
    static class Point{
    int row, col;
    
    Point(int r, int c){
      row = r; col = c;
    }
  }
  
  static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; // 행/열 위,아래,왼,오
  static int N;
  static int[][] board;
  static int cntBlock = 0;
  static ArrayList<Integer> arrCnt = new ArrayList<>();
  static int blockNum;
  static boolean[][] visited;

  // dfs 함수
  static void dfs(int r, int c, int blockNum){
    
    Stack<Point> stack = new Stack<>();
    stack.push(new Point(r,c));
    int cnt = 0;
    
    while(!stack.empty()){
      Point curr = stack.pop();
      if(visited[curr.row][curr.col]) continue; // 방문한 point 라면 pass
      
      visited[curr.row][curr.col] = true;
      cnt++;
  
      for(int i=0; i<4; i++){
        int newr = curr.row + D[i][0];
        int newc = curr.col + D[i][1];
        if(newr < 0 || newr > N-1 || newc < 0 || newc > N-1 ) continue; // 범위를 벗어났으면 pass
        if(visited[newr][newc]) continue; // 이미 방문한 포인트면 pass
        if(board[newr][newc] == 0) { // 0이라면 pass
       //   visited[newr][newc] = true;
          continue;
        }
        
        stack.push(new Point(newr, newc));
      //  board[newr][newc] = blockNum;
   
        // if(!visited[newr][newc]) cnt++;       
      }
    }
    // 한 블록 끝
    arrCnt.add(cnt);
}

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      visited = new boolean[N][N];
      board = new int[N][N];


      for(int i=0; i<N; i++){
        String tmp = br.readLine();
        String[] arr = tmp.split("");
        
        for(int j=0; j<N; j++){
          board[i][j] = Integer.parseInt(arr[j]);
        }
      }
      

   for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
          if(!visited[i][j] && board[i][j] == 1){
            blockNum++;
            dfs(i, j, blockNum);
          }
        }
    }

      System.out.println(blockNum);
      Collections.sort(arrCnt);
      for(int x : arrCnt){
        System.out.println(x);
      }

    }
}

 

생각보다 어려웠는데 이것만 반복해서 익혀도 괜찮겠다 싶을 정도로 기본에 충실한 문제였다. 

내일도 봐야지