백준 온라인 저지 - 2667번: 단지번호붙이기

🔍  문제

---

 

2667번: 단지번호붙이기

 

✏️  풀이 - Java

---

 

이전에 풀었던 미로 탐색과 비슷하면서 조금 다른? 문제였다. 큐를 이용해서 bfs 탐색으로  풀었고 값이 1인 좌표에서만 bfs 탐색을 시작하도록 했다. bfs 탐색 안으로 들어가면, 상하좌우 인접한 아파트 중에 값이 1인 아파트만 큐에 넣어주므로 값이 1인 아파트를 탐색할때마다 cnt++해주어서 개수를 세도록했다. 그리고 마지막에 탐색이 다 끝나고 난 후에는 최종적으로 출력할 list에 cnt값을 추가해주었다. 따라서 list.size()는 총 단지의 개수가 되고, 각 단지별 아파트 개수는  Collection.sort(list)로 list안의 값들을 오름차순 정렬해 준 다음에 출력해주었다. 아직 보자마자 좌르륵 써내려가지는 못해서 조금 더 수련이 필요하다.

 

아, 그리고 다른 분들 코드를 보니  입력받는 메소드, 처리 메소드, 출력 메소드를 각각 따로 만들어서 main method에서는 각 메소드는 호출만해주는 것을 보았다. 너무 문제 푸는데에만 집중해서 생각의 흐름대로 작성하고있다. 나도 다음 작성시에는 그런식으로 작성해야겠다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //지도 크기 입력 받기 
        int n = Integer.parseInt(br.readLine());

        //지도 입력 받기 
        int[][] map = new int[n][n];

        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < n; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        //방문 체크 배열
        boolean[][] c = new boolean[n][n];

        List<Integer> list = new ArrayList<>(); // 결과 값 담을 리스

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1 && !c[i][j]) bfs(map, c, n, list, i, j);
            }
        }

        bw.write(list.size() + "\n"); //단지 개수 출력 

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

        for(int num : list) { // 각 단지별 개수 출력
            bw.write(num + "\n"); 
        }

        bw.flush();
        bw.close();
    }

    private static void bfs(int[][] map, boolean[][] c, int n, List<Integer> list, int x, int y) {
        //상하좌우 배열
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};

        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] {x, y});


        c[x][y] = true;

        int cnt = 1; //아파트 개

        while(!q.isEmpty()) {
            int[] d = q.poll();

            x = d[0];
            y = d[1];


            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 && !c[nx][ny]) {
                        c[nx][ny] = true;
                        q.add(new int[] {nx, ny});
                        cnt++; //개수 1 증가 
                    }
                } 
            }
        }

        list.add(cnt); // 탐색 끝나고 list에 추가해줌 

    }
}