[백준] 2667번: 단지번호붙이기 (Java)

1. 문제설명

정사각형 모양의 지도가 있고 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 이 지도를 보고 상하좌우로 연결된 단지에 번호를 붙이려고 한다. 이 지도에서 나올 수 있는 총 단지 수를 구하고, 각 단지내 집의 수를 오름차순으로 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

⇒ 지도의 인접한 단지들을 모두 구해야 하므로 DFS/BFS를 사용한다.

• 지도 정보를 인접 행렬 형태로 저장한다.
• (1, 1)부터 (N, N)까지 단지의 수와 각 단지 내 집의 수를 구한다.
  • 상하좌우로 이동 가능하고 집이 있는 곳을 DFS 재귀 호출한다.
• 단지 내 집의 수를 List로 저장한다.
  • List의 크기가 “단지 수”
  • List를 오름차순 정렬하여 “단지 내 집의 수”를 출력한다.

 

3. 최종 코드

DFS 풀이

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

public class Main {
    static int n;
    static int[][] map;
    static int count = 1; // 단지 내 집의 수 계산

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void dfs(int a, int b) {
        map[a][b] = 0; // 현재 위치 방문 처리
        count++; // 집의 수 증가

        // 현재 위치의 상하좌우 탐색
        for(int i=0; i<4; i++) {
            int nx = a + dx[i];
            int ny = b + dy[i];
            // 다음 위치가 이동 가능한 범위이고, 집이 있는 경우
            if(nx>0 && nx<=n && ny>0 && ny<=n && map[nx][ny]==1) {
                dfs(nx, ny); // 해당 위치로 재귀 호출
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            String input = br.readLine();
            for(int j=1; j<=n; j++) {
                // 지도의 집 정보를 입력받아 저장
                map[i][j] = input.charAt(j-1) - '0';
            }
        }

        List<Integer> list = new ArrayList<>(); // 단지 내 집의 수 저장
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j] == 1) { // 집이 있는 경우
                    count = 0; // count 초기화
                    dfs(i, j); // dfs 호출
                    list.add(count); // 구한 단지의 집의 수 저장
                }
            }
        }

        list.sort(Comparator.naturalOrder()); // 리스트 오름차순 정렬
        System.out.println(list.size()); // 단지 수
        for(int l : list) {
            System.out.println(l); // 단지 내 집의 수
        }
    }
}

 

BFS 풀이

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

public class Main {
    static int n;
    static int[][] map;
    static int count = 1; // 단지 내 집의 수 계산

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs(int a, int b) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{a, b});
        map[a][b] = 0; // 시작 위치

        while(!q.isEmpty()) {
            int[] cur = q.poll(); // 현재 위치 꺼내기

            for(int i=0; i<4; i++) { // 현재 위치의 상하좌우 탐색
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                // 다음 위치가 이동 가능한 범위이고, 집이 있는 경우
                if(nx>0 && nx<=n && ny>0 && ny<=n && map[nx][ny]==1) {
                    q.add(new int[]{nx, ny}); // 큐에 다음 위치 저장
                    map[nx][ny] = 0; // 방문 처리
                    count++; // 집의 수 증가
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            String input = br.readLine();
            for(int j=1; j<=n; j++) {
                // 지도의 집 정보를 입력받아 저장
                map[i][j] = input.charAt(j-1) - '0';
            }
        }

        List<Integer> list = new ArrayList<>(); // 단지 내 집의 수 저장
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j] == 1) { // 집이 있는 경우
                    count = 1; // count 초기화
                    bfs(i, j); // bfs 호출
                    list.add(count); // 구한 단지의 집의 수 저장
                }
            }
        }

        list.sort(Comparator.naturalOrder()); // 리스트 오름차순 정렬
        System.out.println(list.size()); // 단지 수
        for(int l : list) {
            System.out.println(l); // 단지 내 집의 수
        }
    }
}

 

4. 느낀점 or 기억할정보

List의 정렬

List<Integer> list = new ArrayList<>();

// 오름차순 정렬
list.sort(Comparator.naturalOrder()); 

// 내림차순 정렬
list.sort(Comparator.reverseOrder());

 

List 객체의 sort() 메서드를 사용하여 정렬할 수 있다.

sort()의 파라미터로 Comparator를 사용해 오름차순, 내림차순 정렬을 설정할 수 있다.