[백준 2667번] 단지번호붙이기 (Java 자바) 풀이 방법

백준 2667번 <단지번호붙이기> 문제 보기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

 

백준 2667번 <단지번호붙이> 문제 풀이

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

public class Main {
    
    private static int n;
    private static int[][] map;
    private static int[][] visited;
    private static int check = 0;
    private static ArrayList<Integer> list = new ArrayList<>();
    
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        map = new int[n][n];
        visited = new int[n][n];
        
        for(int i=0; i<n; i++){
            String line = sc.next();
            for(int j=0; j<n; j++){
                map[i][j] = line.charAt(j) - '0';
            }
        }
        
        execute();
        System.out.println(list.size());
        Collections.sort(list);
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }
    }
    
    static void execute(){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 1 && visited[i][j] == 0){
                    check = 1;
                    map[i][j] = 0;
                    visited[i][j] = 1;
                    dfs(i, j);
                    list.add(check);
                }
            }
        }
    }
    
    static void dfs(int x, int y){
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<n){
                if(map[nx][ny] == 1 && visited[nx][ny] == 0){
                    map[nx][ny] = 0;
                    visited[nx][ny] = 1;
                    check++;
                    dfs(nx, ny);
                }
            }
        }
    }
}

 

• 접근 방식
  • 연결된 집을 '단지'라 칭하고 단지 총 개수와 각 단지 별 집의 개수를 세는 문제
  • '연결'에 초점을 맞추고 깊이 우선 탐색 혹은 너비 우선 탐색을 이용하여 문제를 풀 수 있음
  • 자바로 큐를 사용하는 방법을 아직 익히지 않았기에 깊이 우선 탐색으로 문제를 풀게 됨

 

• 코드 설명
  • 방문 여부를 확인하는 visited (int[][]) 2차원함수 사용
  • 집 개수를 세는 check (int) 변수 사용
  • 단지 정보를 담는 list (ArrayList) 사용
  • DFS로 현재 위치가 집이 있는 1일 경우, 다음 탐색에 걸리지 않도록 0으로 바꿔주고, visited 방문 여부도 바꿔줌
  • check를 통해 해당 집과 연결되어 있는 집의 총 개수를 세고 list에 담아줌
  • list의 size가 단지의 총 개수가 되고, list를 정렬하여 출력하면 단지 수를 오름차순으로 결과를 얻을 수 있음

 

• 후기
  • 파이썬으로 문제를 풀어본 경험이 있기 때문에 탐색 방법은 금방 떠올릴 수 있었다
  • 자바로 코딩테스트 언어를 바꾸면서 일반 출력 문제만 주로 풀었었는데 알고리즘 문제를 풀어보니 생각보다 신경써야될 부분이 많았다
  • 게다가, 아직 미숙한 부분이 많아서 코드를 조금 더 객체지향적으로 짜야겠다는 생각이 든다

 

 

 

 

다른 풀이

 

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

public class Main {
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int N;
    public static int[][] graph;
    public static int[][] visited;
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    public static Queue<Node> queue;
    public static ArrayList<Integer> answer;
    
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
      N = Integer.parseInt(br.readLine());
      graph = new int[N][N];
      visited = new int[N][N];
      answer = new ArrayList<>();
      
      for(int i=0; i<N; i++) {
          String info = br.readLine();
          for(int j=0; j<N; j++) {
              graph[i][j] = Character.getNumericValue(info.charAt(j));
          }
      }
      
      for(int i=0; i<N; i++) {
          for(int j=0; j<N; j++) {
              if(graph[i][j] == 1 && visited[i][j] == 0) {
                  answer.add(bfs(i,j));
              }
          }
      }
      
      Collections.sort(answer);
      
      bw.write(String.valueOf(answer.size()) + "\n");
      for(int i=0; i<answer.size(); i++) {
          bw.write(String.valueOf(answer.get(i)) + "\n");
      }
      
      bw.flush();
      bw.close();
    }
    
    static int bfs(int x, int y) {
        int count = 1;
        queue = new LinkedList<>();
        queue.offer(new Node(x,y));
        visited[x][y] = 1;
        
        while(!queue.isEmpty()) {
            Node current = queue.poll();
            
            for(int i=0; i<4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if(0<=nx && nx < N && 0<=ny && ny<N && visited[nx][ny] == 0 && graph[nx][ny] == 1) {
                    count+=1;
                    queue.offer(new Node(nx,ny));
                    visited[nx][ny] = 1;
                }
            }
        }
        
        return count;
    }
}

• Node라는 Class를 만들어 Queue 사용
• BufferedReader / BufferedWriter 사용 → 백준에서 입출력을 더 빠르게 할 수 있음
• LinkedList를 사용하여 너비 우선 탐색 진행