[알고리즘] 백준 2667 단지번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BOJ_2667 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

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

        // read input
        for (int i = 1; i < n + 1; i++) {
            String s = br.readLine();

            for (int j = 1; j < n + 1; j++) {
                map[i][j] = Character.getNumericValue(s.charAt(j - 1));
            }
        }

        List<Integer> list = new ArrayList<Integer>();

        // dfs
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (checkMap(i, j)) {
                    int val = dfs(i, j);
                    list.add(val);
                }
            }
        }

        Collections.sort(list);
        System.out.println(list.size());

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

    public static int dfs(int x, int y) {
        int count = 1;
        visited[x][y] = true;

        if (checkMap(x, y - 1)) {
            count += dfs(x, y - 1); // 상
        }
        if (checkMap(x, y + 1)) {
            count += dfs(x, y + 1); // 하
        }
        if (checkMap(x - 1, y)) {
            count += dfs(x - 1, y); // 좌
        }
        if (checkMap(x + 1, y)) {
            count += dfs(x + 1, y); // 우
        }

        return count;
    }

    public static boolean checkMap(int x, int y) {
        if (x < 0 || y < 0)
            return false;
        if (x > n || y > n)
            return false;
        if (visited[x][y] || map[x][y] == 0)
            return false;

        return true;
    }
}

DFS를 통해 문제를 해결하였다.

 

아파트와 인접하고 있는 상,하,좌,우 값에 대해서 DFS를 돌려야 한다.

 

이중반복문을 통해 입력으로 주어진 이차원 배열(아파트)을 탐색하며

 

해당 인덱스의 값이 1일 경우에 DFS를 돌린다.

 

이 때 인덱스의 값들을 checkMap 메소드를 통해 검증해줘야 한다.

 

마지막으로 DFS가 각각 반환될때마다 List에 넣어준다. List의 size는 총 단지수가 될 것이고 value값은 단지 내 세대의 개수가 될 것이다.

 

BFS로 풀어도 똑같을 것이다~