[BOJ] 2667 단지번호붙이기 - Java

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

2667번: 단지번호붙이기

 

[풀이]

사방으로 이동하면서 연결된 집들의 갯수를 구하는 문제

1. 집들을 모두 ArrayList에 넣어두고, 방문하지 않은 집을 모두 방문하며 dfs를 들어간 횟수를 구한다. (answer)

2. 하나의 집단 탐색이 끝났을 때 총 몇 번 지나왔는지 세기 위해서 전역변수로 count를 두고 새끼dfs를 들어갈 때마다 증가시킨다.

그리고 하나의 집단 탐색이 끝나면 queue에 add (오름차순으로 정렬하기 위해서 PriorityQueue 사용)

 

** 주의 백트래킹처럼 dfs에 인자로 (int count)를 두고 dfs(count+1)로 넘기게 되면, 탐색하다가 이동 가능한 곳이 없는 경우에 끊기게 된다. 그래서 백트래킹처럼 인자로 주면 안되고 전역변수를 둬야함

** 마지막에 PriorityQueue출력하는거 for(int i:queue){ System.out.println(i); } 를 했더니 정렬되지 않은채로 출력되었다. 

poll하거나 iterato를 사용해야 하나보다

 

[코드]

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

public class Main {
    static StringTokenizer st;
    static int N;
    static int[][] Map;
    static ArrayList<Point> Arr = new ArrayList<>();
    static int answer = 0;
    static PriorityQueue<Integer> queue = new PriorityQueue<>();
    static int[] dRow = {-1,1,0,0};
    static int[] dCol = {0,0,-1,1};
    static int count;

    public static void main(String[] args) throws Exception{
        //System.setIn(new FileInputStream("src/main/java/input.txt"));
        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+1][N+1];

        for(int i=1;i<N+1;i++){
            String str = br.readLine();
            for(int j=1;j<N+1;j++){
                Map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j-1)));
                if(Map[i][j] == 1){
                    Arr.add(new Point(i,j));
                }
            }
        }

        for(Point now:Arr){
            if(Map[now.row][now.col]==1){ //이동가능한 집이면
                count = 1;
                answer++;
                Map[now.row][now.col] = 3;
                dfs(now.row,now.col);
                queue.add(count);
            }
        }
        System.out.println(answer);
        while(!queue.isEmpty()){
            System.out.println(queue.poll());
        }
    }

    public static void dfs(int row, int col){
        for(int i=0;i<4;i++){
            int newRow = row + dRow[i];
            int newCol = col + dCol[i];
            if(0<newRow && newRow<=N && 0<newCol && newCol<=N){
                if(Map[newRow][newCol]==1){ //이동가능한 집이면
                    Map[newRow][newCol] = 3; //방문처리
                    count++;
                    dfs(newRow,newCol);
                }
            }
        }
    }

    public static class Point{
        int row;
        int col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}