[소프티어] 장애물 인식 프로그

링크

문제 풀이 bfs

다른 bfs와 다른점은 방문체크 없이 가능하다는 것.
map을 순회하면서 장매물(1)을 찾으면 0으로 변경하여 방문체크와 같은 효과를 얻는다.

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

public class Main {
  static int[] dx = {-1,1,0,0}; 
  static int[] dy = {0,0,-1,1}; 
  static int n, cnt;
  static int[][] map;
  static PriorityQueue<Integer> pq = new PriorityQueue<>();// 블록의 수를 오름차순으로 저장할 우선순위 큐.
  
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());

        map = new int[n][n];

        char[] inp;
        for (int i = 0; i < n; i++) {
            inp = bf.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                map[i][j] = Character.getNumericValue(inp[j]);
            }
        }

      for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              if(map[i][j]!=0){ // 블록인 경우 탐색 시작.
                cnt++; // 블록수 up
                bfs(i,j);
              }
            }
        }
      System.out.println(cnt); // 블록의 개수
       while(!pq.isEmpty()){ // 블록 내 장애물 수 .
         System.out.println(pq.poll());
       }
    }

  public static void bfs(int si,int sj){
    int blockCnt = 0;
    Queue<int[]> q = new LinkedList<>();
    map[si][sj] = 0 ; //땅으로 변경.
    q.offer(new int[]{si,sj}); // 큐에 삽입.
    
    while(!q.isEmpty()){
      blockCnt++;
      // 현재값 꺼냄
      int[] cur = q.poll();
      // 현재기준 4방향 탐색
      for(int dr=0; dr<4;dr++){
        int ni = cur[0] + dx[dr];
        int nj = cur[1] + dy[dr];
        
      // 탐색 후 범위내, 장애물이면 0으로 변경 후 ni,nj를 큐에 삽입한다.

        if(isIn(ni,nj)&&map[ni][nj]!=0){
          map[ni][nj]=0;
          q.offer(new int[]{ni,nj});
        }
      }

      
    }
    // bfs끝나면 우선순위 큐에다가 장애물의 개수를 넣어준다.
     pq.add(blockCnt); 
  }

  // 범위 체크.
  public static boolean isIn(int ni, int nj){
    return (0<=ni&&ni<n)&& (0<=nj&&nj<n);
  }

  // 입력 확인용. 맵 출력문.
    public static void show(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}

level2 문제이지만 오랜만에 감 익히기로 재미있었지만,
확실이 IDE 자동완성 기능이 없이 하려니까 사소한 부분에서 많이 막혀서 어려움을 느꼈으며 자동완성에 많이 의존했던 점을 알았고
이부분을 개선하고자 소프티어에서 많이 문제를 풀어볼 생각이다.
그리고 소프티어 역량평가 합격할 예정!