문제 출처

단계별로 풀어보기 > 그래프와 순회 > 단지번호붙이기
https://www.acmicpc.net/problem/2667

문제 설명

정사각형 모양의 지도에 1은 집이 있는 곳, 0은 집이 없는 곳을 나타낼 때, 연결된 집의 모임을 단지라 정의하고, 그 단지의 갯수와 각 단지별 집의 수를 출력하라.

접근 방법

BFS를 이용한 풀이이다.
x축으로 이동하는 경우 dx, y축으로 이동하는 경우 dy를 각각 정의한다.
2차원 배열을 통해 각 단지의 상태를 저장한 뒤, 2차원 배열 전체를 순회하며 BFS를 진행한다.

BFS는 처음 시작 x,y 좌표 값을 저장하는 Queue를 생성하고, 해당 Queue에서 현재 좌표 기준으로 상하좌우의 상태를 확인하여, 풀이의 3개의 조건에 따라서 진출이 가능한 곳인 경우 visited에 체크 후, Queue에 삽입한다. 이 과정에서 집의 갯수도 필요하므로 count++ 도 실행한다.

이렇게 나온 결과를 list에 저장한 후, 오름차순 정렬하여 출력한다.

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

public class 단지번호붙이기 {
    static int graph[][];
    static int visited[][];
    static int N;

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


    public static int bfs(int sr, int sc){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sr,sc});
        visited[sr][sc] = 1;
        int count = 1;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];

            for(int i = 0; i < 4; i++){
                int nr = r + dx[i];
                int nc = c + dy[i];

                if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if(visited[nr][nc] == 1) continue;
                if(graph[nr][nc] == 0) continue;
                visited[nr][nc] = 1;
                q.add(new int[]{nr,nc});
                count++;
            }
        }
        return count;
    }

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

        N = Integer.parseInt(br.readLine());

        graph = new int[N][N];
        visited = new int[N][N];

        for(int i = 0; i < N; i++){
            String v = br.readLine();
            for(int j = 0; j < N; j++){
                graph[i][j] = v.charAt(j) - '0';
            }
        }

        List<Integer> result = new ArrayList<>();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(graph[i][j] == 1 && visited[i][j] != 1){
                    result.add(bfs(i,j));
                }
            }
        }

        Collections.sort(result);
        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append("\n");

        for(int i = 0; i < result.size(); i++){
            sb.append(result.get(i)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

움직이는 방향을 통해 정의하여 풀이하는 방식에 대해서 알 수 있었다.

해당 풀이의 시간 복잡도는
입력에 O(N^2)
BFS 전체에 O(N^2) -> 탐색 대상이 모든 칸이기 때문
정렬에 O(KlogK) 이므로
O(N^2)이 나온다.

문제푼 흔적