2667번 - 단지번호붙히기

단지번호붙히기라는 문제이다. 간단하게 설명하자면,
아래 그림과 같이 1이 모여있는 부분의 크기를 찾고 오름차순으로 정렬하라는 문제이다.

생각보다 오래걸린 문제였다.
단순하게 주변을 둘러보며 찾는것을 꺼리고 뭔가 더 좋은 방법이 있지 않을까 너무 오랜시간 고민했기 때문이다.

 

혹시나 하는 마음에 풀이를 봤더니... 좀 실망스러웠다. 정말 단순하게 찾는 문제였기 때문이다.

그렇게 방법을 알고 나서 문제를 풀었고, 아래와 같은 코드가 나왔다.

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

public class 단지번호붙이기_2667번 {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static int sum;

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

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        visited = new boolean[N][N];
        sum = 1;
        for(int x=0;x<N;x++) {
            for(int y=0;y<N;y++) {
                if(map[x][y]==1 && !visited[x][y]) {
                    dfs(x,y);
                    queue.add(sum);
                    sum = 1;
                }
            }
        }

        bw.write(queue.size()+"\n");
        while (!queue.isEmpty()) {
            bw.write(queue.poll()+"\n");
        }
        bw.flush();
        bw.close();
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

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

            if(nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny] && map[nx][ny]==1) {
                sum++;
                dfs(nx,ny);
            }
        }
    }
}

 

즉 sum이 더해질동안 계속해서 4 방향을 검사하고 만일 1이 있다면 이미 간 경로에 기록해두며 sum++를 하는 것이다.

풀이를 보며 조금 새롭다고 느낀 것은 배열에 dx, dy를 저장시켜 코드를 간소화 한 점이다.

앞으로 이런 문제가 있으면 적극 채용해야겠다. 코드가 덕분에 많이 간소화 된 듯 하다.