99클럽 코테 스터디 18일차 TIL , 단지번호붙이기

문제

풀이

입력 N이 주어지고 NxN 하는 지도에 집이 있는 곳들이 입력된다.

좌우상하로 집이 있다면 이는 같은 단지가 된다.

단지의 개수와 각 단지의 아파트 개수를 오름차순으로 return 하면 된다.

제출 1 - 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    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+1][n+1];
        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j+1] = line.charAt(j) - '0';
            }
        }

        bfs(n,map);

    }

    private static void bfs(int n, int[][] map) {
        List<Integer> answer = new ArrayList<>();
        int group = 0;

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


        for(int i=1;i<=n;i++){
            for (int j = 1; j <= n; j++) {
                if(map[i][j] == 0) continue;
                Deque<int[]> que = new ArrayDeque<>();
                que.offer(new int[]{i,j});
                int cnt = 1;
                map[i][j] = 0;
                group++;

                while(!que.isEmpty()){
                    int[] xy = que.poll();
                    for (int k = 0; k < 4; k++) {
                        int nx = xy[0] + dx[k];
                        int ny = xy[1] + dy[k];
                        if(nx > 0 && ny > 0 && nx <= n && ny <= n && map[nx][ny] != 0){
                            map[nx][ny] = 0;
                            cnt++;
                            que.offer(new int[]{nx,ny});
                        }
                    }
                }

                answer.add(cnt);
            }
        }

        answer.sort(Comparator.naturalOrder());
        System.out.println(group);
        for(int x : answer) System.out.println(x);

    }
}

 

BFS로 문제 해결.

map 전체를 돌면서 1이 발견됐을 때 while문을 다시 한번 돌아 단지 내 집의 개수를 세서 넣는다.

문제 해결은 생각보다 빨리했는데 계속 틀렸다 그래서 시간이 지체됐는데,

이걸 못봤다..

TIL

• 문제를 아직도 설렁설렁 보다니..
• BFS