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

문제 링크

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

나의 기록

✅ 알고리즘 분류 : BFS

✅ 성공 여부 : ✔

✅ 문제 난이도 : 실버1

✅ 체감 난이도 : Normal

접근 방법

주어진 map을 완전탐색하며 군집화하는 것이 문제의 목표이다.

때문에 BFS와 DFS 중 선택할 수 있었는데, 나는 BFS를 활용하여 문제를 풀었다.

map의 모든 좌표를 시작점으로 하여 BFS를 수행해야 하는데, 시작점 map[i][j]가 0일 경우에는 바로 함수를 종료하고, 아닐 경우에는 BFS를 시작한다. visit 배열을 사용하여 단지 중복 체크가 되지 않도록 했다.

하나의 BFS가 종료되면 하나의 지역에 대한 군집화가 끝난 것이므로, ans로 지칭한 ArrayList에 해당 지역의 단지 수 cnt를 저장한다.

 

여기서 그냥 출...력하면 안되고! 문제의 조건을 잘 읽어봐야 한다.

"오름차순으로 정렬하여 출력"

이것때문에 한 번 틀렸다. 문제의 조건을 꼼꼼히 읽어보자...

 

코드

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

public class bj2667_단지번호붙이기 {
    static class Point{
        int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int[] di = {-1,1,0,0};
    static int[] dj = {0,0,-1,1};
    static int N, num = 1;
    static List<Integer> ans = new ArrayList<>();
    static int[][] map;
    static boolean[][] visited;
    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][N];
        visited = new boolean[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';
            }
        }

        // 모든 좌표에 대해 BFS 수행
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                bfs(new Point(i,j));
            }
        }

        // 정답 출력
        System.out.println(ans.size());
        Collections.sort(ans);
        for(int a : ans){
            System.out.println(a);
        }
    }

    public static void bfs(Point start){
        // 집이 없거나, 이미 방문한 집이면 return
        if(map[start.x][start.y] == 0 || visited[start.x][start.y]) return;

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(start.x, start.y));
        visited[start.x][start.y] = true;

        int cnt = 0; // 단지에 속한 집의 수
        while(!queue.isEmpty()){
            Point now = queue.poll();
            cnt++;

            for(int d = 0 ; d < 4 ; d++){
                int nx = now.x + di[d];
                int ny = now.y + dj[d];
                if(isValid(nx, ny)){
                    queue.add(new Point(nx, ny));
                    visited[nx][ny] = true;
                }
            }
        }

        ans.add(cnt);
        num++;
    }

    public static boolean isValid(int x, int y){
        return x >= 0 && x < N && y >= 0 && y < N && map[x][y] != 0 && !visited[x][y];
    }
}