[JAVA] 백준 2667

 

 

 

 

2667번: 단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

풀이

해당 문제는 연결된 노드들끼리 묶어서 해당 묶음들의 수와 묶음들이 가진 노드들의 수를 출력하는 문제였습니다.

따라서 저는 BFS를 활용하여 문제를 해결하였습니다.

📌 입력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+2;
        A = new int[N][N];
        V = new boolean[N][N];
        l = new LinkedList<>();
        N -= 1;
        for(int i=1; i<N; i++){
            String value = br.readLine();
            for(int j=1; j<N; j++){
                A[i][j] = Integer.parseInt(value.charAt(j-1)+"");
            }
        }

탐색을 하는 과정에서 ArrayIndexOutOfBoundsException를 예방하기 위해서 배열의 크기를 2만큼 추가해주고 값을 1 ~ N-1이전까지 담아두도록 만들었습니다.

• A : 지도를 담아두는 배열
• V : 해당 지역을 방문한지 여부
• l : 정답을 담는 리스트

📌 BFS

    public static void BFS(Node x){
        if(A[x.x][x.y] == 0 || V[x.x][x.y]) return ;
        Queue<Node> q = new LinkedList<>();

        int count = 1;
        q.add(x);
        V[x.x][x.y] = true;
        while (!q.isEmpty()){
            Node now = q.poll();
            for(int i=0; i<4; i++){
                int a = now.x + xValue[i];
                int b = now.y + yValue[i];
                if(A[a][b] == 1 && !V[a][b]){
                    count++;
                    V[a][b] = true;
                    q.add(new Node(a, b));
                }
            }
        }
        l.add(count);
    }

만약 현재 지역이 0이거나 이미 방문한 지역이라면 메서드를 종료한다.

그 후 BFS와 비슷하게 동작하는데

• xValue와 yValue를 통해서 동서남북을 탐색한다.
• 만약 동서남북을 돌면서 1인 지역이고 방문한 적이 없는 지역이 있다면 queue에 추가해주고 카운트해준다. (방문 여부도 체크)
• 모든 탐색을 종료하면 정답 리스트에 값을 추가해준다.

이 탐색을 모든 지역에서 실행해준다.

이 방식 말고도 DFS로 푼 방식이 아래에 나와있다 DFS가 좀 더 빨랐다.

📌 출력

         StringBuilder sb = new StringBuilder();
        Collections.sort(l);
        sb.append(l.size()).append("\n");
        for(int i=0; i<l.size(); i++){
            sb.append(l.get(i)).append("\n");
        }
        System.out.println(sb);

Collections 인터페이스의 sort 메서드로 오름차순 정렬 후 리스트 원소 수와 값을 출력해준다.

📌 전체 코드

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

class Main {
    static int[][] A;
    static boolean[][] V;
    static LinkedList<Integer> l;
    static int[] xValue = {0, 1, -1, 0};
    static int[] yValue = {1, 0, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+2;
        A = new int[N][N];
        V = new boolean[N][N];
        l = new LinkedList<>();
        N -= 1;
        for(int i=1; i<N; i++){
            String value = br.readLine();
            for(int j=1; j<N; j++){
                A[i][j] = Integer.parseInt(value.charAt(j-1)+"");
            }
        }
        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                BFS(new Node(i, j));
            }
        }

        StringBuilder sb = new StringBuilder();
        Collections.sort(l);
        sb.append(l.size()).append("\n");
        for(int i=0; i<l.size(); i++){
            sb.append(l.get(i)).append("\n");
        }
        System.out.println(sb);

    }

    public static void BFS(Node x){
        if(A[x.x][x.y] == 0 || V[x.x][x.y]) return ;
        Queue<Node> q = new LinkedList<>();

        int count = 1;
        q.add(x);
        V[x.x][x.y] = true;
        while (!q.isEmpty()){
            Node now = q.poll();
            for(int i=0; i<4; i++){
                int a = now.x + xValue[i];
                int b = now.y + yValue[i];
                if(A[a][b] == 1 && !V[a][b]){
                    count++;
                    V[a][b] = true;
                    q.add(new Node(a, b));
                }
            }
        }
        l.add(count);
    }

    static class Node{
        int x;
        int y;

        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

}

📌 DFS 방식으로 해결한 방법

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

class Main {
    static int[][] A;
    static LinkedList<Integer> l;
    static int[] xValue = {0, 1, -1, 0};
    static int[] yValue = {1, 0, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+2;
        A = new int[N][N];
        l = new LinkedList<>();
        N -= 1;

        for(int i=1; i<N; i++){
            String value = br.readLine();
            for(int j=1; j<N; j++){
                A[i][j] = Integer.parseInt(value.charAt(j-1)+"");
            }
        }
        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                int value = DFS(i, j);
                if(value != 0) l.add(value);
            }
        }

        StringBuilder sb = new StringBuilder();

        Collections.sort(l);
        sb.append(l.size()).append("\n");
        for(int i=0; i<l.size(); i++){
            sb.append(l.get(i)).append("\n");
        }
        System.out.println(sb);

    }

    public static int DFS(int x, int y){
        if(A[x][y] == 0) return 0;

        A[x][y] = 0;
        int count = 1;
        for(int i=0; i<4; i++){
            count += DFS(x + xValue[i], y + yValue[i]);
        }
        return count;
    }

}

결과

BFS

DFS