BOJ - 단지번호붙이기 (2667)

• 그래프 문제이다.
  • 탐색 + 연결 요소 정보 이용하여 풀었다.
  • 연결요소의 개수 문제에서 조금 생각하면 된다.
  • 문제에서 오름차순 조건을 기억하자.
  • https://developer-h.tistory.com/entry/BOJ-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C%EC%9D%98-%EA%B0%9C%EC%88%98-11724

BOJ - 연결 요소의 개수 (11724)

 

• import java.util.ArrayList;
  import java.util.List;
  import java.util.Scanner;
  import java.util.stream.Collectors;
  
  
  public class Main {
      public static final Scanner scanner = new Scanner(System.in);
  
      public static final int NO_EXIST = 0;
  
      public static void main(String[] args) throws Exception {
          int V = scanner.nextInt();
  
          int[][] map = new int[V + 1][V + 1];
          boolean[][] visited = new boolean[V + 1][V + 1];
  
          for (int i = 1; i <= V; i += 1) {
              String line = scanner.next();
              char[] chars = line.toCharArray();
              for (int j = 0; j < chars.length; j++) {
                  map[i][j + 1] = Character.getNumericValue(chars[j]);
              }
          }
  
          ArrayList<Integer> answers = new ArrayList<>();
  
          for (int i = 1; i <= V; i++) {
              for (int j = 1; j <= V; j += 1) {
                  if (map[i][j] != NO_EXIST && visited[i][j] == false) {
                      ArrayList<String> visitedPath = new ArrayList<>();
                      dfsRecursive(i, j, map, visited, visitedPath);
                      answers.add(visitedPath.size());
                  }
              }
          }
  
          //개수 출력
          System.out.println(answers.size());
          
          //오름차순
          List<Integer> collect = answers.stream().sorted().collect(Collectors.toList());
          for(int i = 0 ; i < collect.size(); i++) {
              System.out.println(collect.get(i));
          }
      }
  
      private static void dfsRecursive(int r, int c, int[][] map, boolean[][] visited, ArrayList<String> visitedPath) {
          //탐색 종료
          if (r >= map.length || r <= 0) return;
          if (c >= map.length || c <= 0) return;
          if (map[r][c] == NO_EXIST) return;
          if (visited[r][c] == true) return;
  
          //방문 표시
          visited[r][c] = true;
  
          //방문 정보 저장
          visitedPath.add(String.format("%d -> %d", r, c));
  
          //인접 다음노드 탐색 상, 하, 좌, 우
          dfsRecursive(r + 1, c, map, visited, visitedPath);
          dfsRecursive(r - 1, c, map, visited, visitedPath);
          dfsRecursive(r, c - 1, map, visited, visitedPath);
          dfsRecursive(r, c + 1, map, visited, visitedPath);
      }
  }