[JAVA] 백준 2667 단지번호붙이기

 

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

 

문제분석

DFS/BFS 연습용 문제를 풀기 위해 이 문제를 정했다. 문제를 보면 단지를 구하는 것이다. 단지를 그래프라고 생각하고, 그래프를 전부 순회하도록 코드를 작성하면 된다. 따라서 DFS/BFS 둘 중 아무거나 선택해도 문제를 풀 수 있게 되어있다. DFS/BFS를 공부하며 배운 구조를 활용하여 문제를 해결하면 될 것이라 생각했다.

구현에서, queue에 뭘 저장해야 하나 고민했었는데, 문제에서 주어진 N의 최대값이 25인 점을 활용하여, row*25+col값을 저장하고, poll한 뒤 25로 나눈 몫과 나머지를 적용할 수 있게끔 하였다.

 

코드

BFS< - >DFS 바꾸기 용이하다.

BFS용 메서드 offer과 poll 대신

DFS용 메서드 push와 pop을 사용하면 완벽히 치환된다. 결과는 당연히 같게 나온다.

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];
        boolean[][] visited = new boolean[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(visited[i],false);
        }

        for(int i = 0; i < N; i++){
            String temp = br.readLine();
            for(int j = 0; j < N; j++){
                arr[i][j] = temp.charAt(j)-'0'; // char->int를 위함. 0과 1은 UTF-16기준 1 차이 남.
            }
        }

        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        ArrayList<Integer> ans = new ArrayList<Integer>();
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){ // arr [i][j]부터 탐색해 나아감.
                if(arr[i][j]==1 && !visited[i][j]){ // 한번도 방문 안한 곳+집이 있는 경우
                    //System.out.println("queue실행, 시작 row, col : "+i+", "+j);
                    visited[i][j]=true;
                    queue.offer(25*i+j);
                    int count = 1;

                    while(!queue.isEmpty()){ // 단지 탐색 시작. 4개 방향으로 탐색
                        int house = queue.poll();
                        int row = house/25;
                        int col = house%25;
                        if(row==0){ // row 만 +1 탐색
                            if(!visited[row+1][col]&&arr[row+1][col]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row+1)+col);
                                visited[row+1][col] = true;
                            }
                        }else if(row==N-1){// row 만 -1 탐색
                            if(!visited[row-1][col]&&arr[row-1][col]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row-1)+col);
                                visited[row-1][col] = true;
                            }
                        }else{ // row 만 +1 -1 탐색
                            if(!visited[row+1][col]&&arr[row+1][col]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row+1)+col);
                                visited[row+1][col] = true;
                            }
                            if(!visited[row-1][col]&&arr[row-1][col]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row-1)+col);
                                visited[row-1][col] = true;
                            }
                        }

                        if(col==0){ // col 만 +1 탐색
                            if(!visited[row][col+1]&&arr[row][col+1]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row)+col+1);
                                visited[row][col+1] = true;
                            }
                        }else if(col==N-1){ // col 만 -1 탐색
                            if(!visited[row][col-1]&&arr[row][col-1]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row)+col-1);
                                visited[row][col-1] = true;
                            }                        
                        }else{ // col 만 +1 -1 탐색
                            if(!visited[row][col+1]&&arr[row][col+1]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row)+col+1);
                                visited[row][col+1] = true;
                            }
                            if(!visited[row][col-1]&&arr[row][col-1]==1){// 미탐색+이어진 경우
                                count +=1;
                                queue.offer(25*(row)+col-1);
                                visited[row][col-1] = true;
                            }
                        }
                    }

                    ans.add(count);
                }
            }
        }
        ans.sort((a,b)->a-b);
        bw.write(String.valueOf((ans.size())));
        for(int i = 0; i < ans.size(); i++){
            bw.newLine();
            bw.write(String.valueOf(ans.get(i)));
        }
        bw.flush();
        bw.close();

    }
}