단지번호붙이기 - 백준(2667, 그래프 탐색)

🎯 단지번호붙이기

단지번호붙이기 - 2667, 그래프 탐색, 실버1

🧐 알고리즘[접근방법]

1. 장점의 개수로 2차원 배열 선언

2. 배열 탐색하면서 단지 구분 하여 탐색

   • 탐색하면서 단지안에 집 개수 저장

3. 집 개수 정렬 후 출력

👨‍💻 소스

BFS 소스

import java.util.*;

public class Main {

  public static class Node {
    int x;
    int y;
    
    Node(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  
  public static int N;
  
  public static int[][] map;
  public static boolean[][] check;
  
  public static final int[] dx = {0, 0, -1, 1};
  public static final int[] dy = {-1, 1, 0, 0};
  
  public static int index = 1;
  public static ArrayList<Node> houseList = new ArrayList<Node>();
  
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);
    
    N = sc.nextInt();
    sc.nextLine();
    
    map = new int[N][N];
    
    for(int i = 0 ; i < map.length ; i++) {
      String s = sc.nextLine();
      for(int j = 0 ; j < N ; j++) {
        map[i][j] = s.charAt(j) - '0';
      }
    }
    
    check = new boolean[N][N];
    
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = 0 ; i < N ; i++) {
      for(int j = 0 ; j < N ; j++) {
        if(map[i][j] == 1 && !check[i][j]) {
          list.add(BFS(new Node(i, j)));
        }
      }
    }
    
    Collections.sort(list);
    
    System.out.println(list.size());
    for(int i = 0 ; i < list.size() ; i++) {
      System.out.println(list.get(i));
    }
    
  }
  
  public static int BFS(Node node) {
    
    index++;

    Queue<Node> q = new LinkedList<Node>();
    q.add(node);
    map[node.x][node.y] = index;
    check[node.x][node.y] = true;
    
    int count = 1;
    while(!q.isEmpty()) {
      Node n = q.poll();
      
      for(int i = 0 ; i < dx.length ; i++) {
        int x = n.x + dx[i];
        int y = n.y + dy[i];
        
        if(0 <= x && x < N && 0 <= y && y < N) {
          if(map[x][y] == 1 && !check[x][y]) {
            map[x][y] = index;
            check[x][y] = true;
            q.add(new Node(x, y));
            count++;
          }
        }
      }
    }
    
    return count;
  }
  
}

DFS 소스

import java.util.*;

public class Main {

  public static class Node {
    int x;
    int y;
    
    Node(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  
  public static int N;
  
  public static int[][] map;
  public static boolean[][] check;
  
  public static final int[] dx = {0, 0, -1, 1};
  public static final int[] dy = {-1, 1, 0, 0};
  
  public static int index = 1;
  public static ArrayList<Node> houseList = new ArrayList<Node>();
  
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);
    
    N = sc.nextInt();
    sc.nextLine();
    
    map = new int[N][N];
    
    for(int i = 0 ; i < map.length ; i++) {
      String s = sc.nextLine();
      for(int j = 0 ; j < N ; j++) {
        map[i][j] = s.charAt(j) - '0';
      }
    }
    
    check = new boolean[N][N];
    
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = 0 ; i < N ; i++) {
      for(int j = 0 ; j < N ; j++) {
        if(map[i][j] == 1 && !check[i][j]) {
          list.add(DFS(new Node(i, j)));
        }
      }
    }
        
    Collections.sort(list);
    
    System.out.println(list.size());
    for(int i = 0 ; i < list.size() ; i++) {
      System.out.println(list.get(i));
    }
    
  }
  
  public static int DFS(Node node) {
    
    int count = 1;
    map[node.x][node.y] = index;
    check[node.x][node.y] = true;
    
    for(int i = 0 ; i < dx.length ; i++) {
      int x = node.x + dx[i];
      int y = node.y + dy[i];
      
      if(0 <= x && x < N && 0 <= y && y < N) {
        if(map[x][y] == 1 && !check[x][y]) {
          map[x][y] = index;
          check[x][y] = true;
          count += DFS(new Node(x, y));
        }
      }
    }
    
    return count;
  }
  
}

🏅 결과

• BFS 결과
  

• DFS 결과
  

📖 관련 지식