[Baekjoon] 2667 - 단지번호붙이기

📝 문제

 

 

 

❗ 주의

· charAt()의 반환형은 char형이다. 그러므로 int형 배열에 그대로 넣으면 안된다. -'0'을 꼭 해서 넣어주자. 안그러면 0은 48, 1은 49의 값으로 들어간다.

 

 

🔑 풀이 과정

예전 연결 요소의 개수 문제를 2차원으로 만든듯한 문제.

· 우리가 구해야 할 것: 총 단지의 수, 그리고 단지내 집의 수를 오름차순으로 정렬한 것! 단지내 집의 수를 정렬을 해야하므로 따로 저장할 자료구조가 필요하다.

 

· 이 문제는 DFS, BFS 다 가능한데, 나는 BFS방식으로 풀이했다.

 

· 총 단지의 수는, N*N 크기의 지도를 순회하면서, 값이 1이고(집이 있는 경우) 방문 배열이 false일때 단지의 수를 하나씩 증가시켰다.

<순회할 때의 경우들>

① 값이 0일때: 집이 없다는 뜻으로 pass

② 값이 1이고, 방문배열이 false: 집이 있고, 아직 방문하지 않았으므로 탐색하면 된다.

③ 값이 1이고, 방문배열이 true: 집은 있으나, 앞서 다른단지를 탐색하면서 탐색된 곳이므로 탐색할 필요가 없다.

 

· 단지내 집의 수는, 한 번 BFS가 일어나면 한 단지를 탐색하는것이므로, BFS 메서드 내에 변수를 하나 두고 큐에 요소가 하나씩 들어갈 때마다 (연결된 집이 있을때마다) 변수를 증가시켰다. 그리고 BFS 메서드가 종료될 때 그 변수를 반환하게끔 만들었다.

 

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

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

    static int N;

    static int[][] arr;
    static boolean[][] visited;

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

        //입력
        N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        visited = new boolean[N][N]; //방문 배열

        for(int i = 0; i < N; i++){
            String str = br.readLine();

            for(int j = 0; j < N; j++)
                arr[i][j] = str.charAt(j) - '0'; //str.charAt의 반환형은 char니까 정수로 변환하기 위해서 꼭 - '0' 해주기.

        }
        //---입력 종료

        //탐색
        int count = 0; //총 단지수를 저장할 변수
        ArrayList<Integer> arrayList = new ArrayList<>(); //단지내 집 수 저장
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if((arr[i][j] == 1) && (!visited[i][j])){
                    count++;
                    arrayList.add(BFS(i, j));
                }
            }
        }

        sb.append(count).append("\n");

        //단지내 집 수를 오름차순으로 정렬해야 함
        Collections.sort(arrayList);

        for(int num: arrayList)
            sb.append(num).append("\n");

        //출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    //BFS 메서드
    static int BFS(int i, int j){
        int sum = 0; //단지 내 집의 수를 저장할 배열

        Queue<int[]> queue = new LinkedList<>();
        visited[i][j] = true;
        queue.add(new int[] {i, j});
        sum++;

        while(!queue.isEmpty()){
            int[] now = queue.remove();

            for(int k = 0; k < 4; k++){ //상하좌우 확인
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if((x >= 0) && (x < N) && (y >= 0) && (y < N)){
                    if((arr[x][y] == 1) && (!visited[x][y])){
                        visited[x][y] = true;
                        queue.add(new int[] {x, y});
                        sum++;
                    }
                }
            }
        }

        return sum;

    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색