BOJ_2667 단지번호붙이기 [Java] (S1)

문제 설명

풀이

BFS, DFS로 모두 풀 수 있는 문제이다. 일단 그래프 문제인 것은 바로 알 수 있고, 특별히 어느 것을 골라도 상관없을 듯하다.

 

풀이는, 일단 한 점을 잡고 쭉 DFS, BFS를 돌린다. 그러면 붙어있는 것들은 모두 visit = true가 될 것이고, 다음 탐색을 하면서 또 함수를 돌리고, 이렇게 반복하면 쉽게 풀 수 있다.

 

코드

BFS

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

public class Main {
    private static int dx[] = {0,0,1,-1};
    private static int dy[] = {1,-1,0,0};
    private static int[] aparts = new int[25*25];
    private static int n;
    private static int apartNum = 0; //아파트 단지 번호의 수
    private static boolean[][] visited = new boolean[25][25]; //방문여부
    private static int[][] map = new int[25][25]; //지도

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        map = new int[n][n];
        visited = new boolean[n][n];

        //전체 사각형 입력 받기
        for(int i=0; i<n; i++){
            String input = sc.next();
            for(int j=0; j<n; j++){
                map[i][j] = input.charAt(j)-'0';
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    apartNum++;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(aparts);
        System.out.println(apartNum);

        for(int i=0; i<aparts.length; i++){
            if(aparts[i] == 0){
            }else{
                System.out.println(aparts[i]);
            }
        }

    }

    private static void bfs(int x, int y) {
        //2차원 LinkedList를 가진 큐 선언
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x,y});
        visited[x][y] = true;
        aparts[apartNum]++;

        while(!que.isEmpty()){

            //x, y 값을 받아오기 위한 방법
            int curX = que.peek()[0];
            int curY = que.peek()[1];
            que.poll();

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

                if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                    if(map[nx][ny] == 1 && !visited[nx][ny]){
                        que.add(new int[]{nx,ny});
                        visited[nx][ny] = true;
                        aparts[apartNum]++;
                    }
                }
            }
        }
    }
}

DFS

 

2667번: 단지번호붙이기

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

public class Main {
    private static int num;
    private static int[][] map;
    private static int n;
    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+2][n+2];
        for (int i = 1; i <= n; ++i) {
            char[] t = br.readLine().toCharArray();
            for (int j = 1; j <= n; ++j) {
                map[i][j] = t[j-1]-'0';
            }
        }
        br.close();
        num = 2;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                    ++num;
                }
            }
        }
        int[] nums = new int[num];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] !=  0) {
                    ++nums[map[i][j]-2];
                }
            }
        }
        Arrays.sort(nums);
        num = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[num++] = nums[i];
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(num));
        bw.newLine();
        for (int i = 0; i < num; ++i) {
            bw.write(String.valueOf(nums[i]));
            bw.newLine();
        }
        bw.close();
    }

    private static void dfs(int i, int j) {
        map[i][j] = num;
        if (map[i+1][j] == 1)
            dfs(i+1, j);
        if (map[i-1][j] == 1)
            dfs(i-1, j);
        if (map[i][j+1] == 1)
            dfs(i, j+1);
        if (map[i][j-1] == 1)
            dfs(i, j-1);
    }
}

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

2667번: 단지번호붙이기