알고리즘 풀이 - 백준 2667(단지번호붙이기, 그래프(DFS, BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

정사각형 모양의 지도에 1은 집이 있고 0은 없는 곳이다. 좌우 / 상하로 이어진 경우에 연결된 모든 집들은 하나의 단지라고 할 때, 각 단지에 있는 집의 수를 오름차순으로 정렬하여 출력하는 문제

 

 

2. 풀이

 

이 문제는 인접한 모든 아파트를 찾아서 하나의 단지로 묶어내야 하는 문제이다.

따라서, 주어진 값이 하나의 행렬 형태로 주어지므로 인접 행렬로 정보를 저장한 뒤 서로 인접한 모든 정점을 찾아 그 개수를 저장한다.

정점을 찾을 때는 DFS 또는 BFS를 이용하여 그래프 탐색을 수행하면 된다.

 

각 위치에서 탐색을 시작하여 연결된 것의 개수를 모두 합치면 하나의 단지 내 아파트의 개수를 알 수 있게 된다. 아래의 코드에서 정확한 방법을 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① DFS로 구현

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    static String[] map;
    static int n;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    
    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 String[n];
        for(int i=0; i < n; i++){
            map[i] = br.readLine();
        }

        visited = new boolean[n][n];

        ArrayList<Integer> ans = new ArrayList<>();
        
        // 정사각형 내 모든 위치에서 단지를 찾아야함
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                // 이미 다른 단지로 포함되었거나, 아파트가 아닌 경우는 넘어가자.
                if(visited[i][j] || map[i].charAt(j) == '0') continue;
                visited[i][j] = true;
                ans.add(dfs(i, j, 1));
            }
        }
        
        // 단지의 개수를 우선 써내리고 정렬 수행
        bw.write(String.valueOf(ans.size()) + "\n");
        Collections.sort(ans);

        for(int i : ans){
            bw.write(String.valueOf(i) + "\n");
        }
        bw.flush();
        br.close();
    }

    // DFS를 통해 단지를 찾아낸다.
    // i, j는 index 값이며 prox는 인접한 아파트의 현재 개수
    // 탐색을 시작할 때는 자기 자신만 인접한 것이므로 1을 전달함
    private static int dfs(int i, int j, int prox){
        int temp = prox;
        
        // 위의 dy, dx 배열을 통해 다음으로 탐색할 위치를 지정
        for(int k=0; k < 4; k++){
            int ny = i + dy[k];
            int nx = j + dx[k];
            
            // 범위 안에 있으며 아직 방문되지 않았고 아파트인 경우에만 추가 탐색 수행
            if(0 <= ny && ny < n && 0 <= nx && nx < n && !visited[ny][nx] && map[ny].charAt(nx) == '1'){
                visited[ny][nx] = true;
                temp += dfs(ny, nx, 1);
                
            }
        }

        // 상하좌우 4방향으로 탐색 후 찾은 인접 아파트 개수를 모두 더한 것을 반환한다.
        return temp;
    }
}

 

② BFS로 구현

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    static String[] map;
    static int n;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    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 String[n];
        for(int i=0; i < n; i++){
            map[i] = br.readLine();
        }

        visited = new boolean[n][n];

        ArrayList<Integer> ans = new ArrayList<>();

        // 정사각형 내 모든 위치에서 단지를 찾아야함
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                // 이미 다른 단지로 포함되었거나, 아파트가 아닌 경우는 넘어가자.
                if(visited[i][j] || map[i].charAt(j) == '0') continue;
                visited[i][j] = true;
                ans.add(bfs(i, j));
            }
        }

        // 단지의 개수를 우선 써내리고 정렬 수행
        bw.write(String.valueOf(ans.size()) + "\n");
        Collections.sort(ans);

        for(int i : ans){
            bw.write(String.valueOf(i) + "\n");
        }
        bw.flush();
        br.close();
    }

    // BFS를 통해 단지를 찾아낸다.
    // i, j는 위치 index
    private static int bfs(int i, int j){
        Queue<Map> q = new LinkedList<>();
        q.offer(new Map(i, j));

        // i, j는 우선 아파트 이므로 1에서 시작
        int complex = 1;
        while(!q.isEmpty()){
            Map curr = q.poll();

            int y = curr.y;
            int x = curr.x;

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

                // 다음 방문 위치가 범위 안이고, 미방문 상태이며 아파트일 때만 탐색
                if(0 <= ny && ny < n && 0 <= nx && nx < n && !visited[ny][nx] && map[ny].charAt(nx) == '1'){
                    q.offer(new Map(ny, nx));
                    visited[ny][nx] = true;
                    complex++;
                }
            }
        }
        return complex;
    }
}

// 별도의 Class를 통해 y, x 위치값을 저장하여 그 자체를 Queue에 넣어서 탐색 수행
class Map{
    int y;
    int x;
    public Map(int y, int x){
        this.y = y;
        this.x = x;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.