[Algorithm] 99클럽 코테 스터디 8일차 TIL | 백준_단지번호붙이기(2667번)

 

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

---

N x N 크기의 map을 선언하고

0또는 1값을 배열에 넣어준다.

 

단지 내 집의 수를 count 변수로, 

총 단지수를 total 변수로 선언하였다.

 

단지 내 집의 수를 오름차순으로 정렬하여 출력해야하므로 PriorityQueue를 사용하였다.

 

map에서 방문 처리는 map[i][j]=0으로 값을 바꿔주고, map이 0보다 큰 값인 위치의 배열값만 검사하도록 한다!

 

처음에 3%에서 틀렸습니다가 나왔는데

단지 내 처음 집을 찾았을 때 방문 처리를 하지 않았던 것이 원인이었다..!!

for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
        if(map[i][j] > 0){
            count = 1; 
            map[i][j] = 0; //방문처리
            total++;
            dfs(map, i, j, N);
            pq.add(count);
        }
    }
}

 

전체 풀이

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

class Main{
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < N; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }
        int total = 0;
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] > 0){
                    count = 1;
                    map[i][j] = 0;
                    total++;
                    dfs(map, i, j, N);
                    pq.add(count);
                }
            }
        }
        sb.append(total);
        while(!pq.isEmpty()){
            sb.append("\n").append(pq.poll());
        }
        System.out.println(sb);
    }
    public static void dfs(int[][] map, int x, int y, int N){
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        for(int i = 0; i < 4; i++){
            int dx_x = x + dx[i];
            int dy_y = y + dy[i];

            if(dx_x >= 0 && dx_x < N && dy_y >= 0 && dy_y < N){
                if(map[dx_x][dy_y] > 0){
                    count++;
                    map[dx_x][dy_y] = 0;
                    dfs(map, dx_x, dy_y, N);
                }
            }
        }
    }
}

 

단지 내 오름차순이 문제의 조건이었음을 제출 후 알게되었다..문제를 꼼꼼히 읽어야겠따