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

문제

---

이번에 다뤄볼 문제는 2667번 문제 '단지번호붙이기'입니다.

단지번호붙이기 문제에서 연습해야 하는 key-point는 DFS입니다.

 

DFS(깊이 우선 탐색)이란  맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식입니다.

 

문제에서 원하는건 총 몇개의 단지가 존재하는지, 그리고 그 단지들이 갖고있는 각 집의 총 수를 오름차순 정렬으로 보여달라 입니다.

제공받은 map을 순회하며 집을 뜻하는 1을 만날경우 해당 포인트에서 바로 깊이우선탐색을 시작합니다.

탐색을 시작하는 포인트에서부터 상,하,좌,우에 위치한 노드를 탐색하며 제공된 map을 벗어나는 위치를 탐색하려 할 경우 무시합니다.

이렇게 진행을 할 경우 한번 탐색을 시작했을때 단지 하나를 완전히 파악 할 수 있습니다.

(탐색이 진행된 곳은 2로 값을 바꿔놓기 때문에 같은 단지를 다시 탐색하지 않습니다.)

 

또한 문제의 요구사항에서 어느 단지에 몇개의 집이 있는지를 요구한적은 없기때문에 단지와 집의 개수는 연관성을 맺을 필요가 없습니다.

따라서 한번 탐색을 하며(=하나의 단지) 만난 집의 총 개수를 따로 List에 저장해두고 마지막에 Sort하여 출력함으로써 마무리 합니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static int n;
    private static int houseCount = 1;
    private static final int[] dirX = {-1, 1, 0, 0};
    private static final int[] dirY = {0, 0, 1, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < n; j++) {
                map[i][j] = Character.getNumericValue(line.charAt(j));
            }
        }

        int danjiCount = 0;
        List<Integer> houseCountList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) {
                    danjiCount++;
                    dfs(map, i, j);
                    houseCountList.add(houseCount);
                    houseCount = 1;
                }
            }
        }
        System.out.println(danjiCount);
        houseCountList.stream().sorted().forEach(System.out::println);
    }

    private static void dfs(int[][] map, int x, int y) {
        map[x][y] = 2; //탐색됨을 마킹하는 용도
        for (int i = 0; i < 4; i++) {
            int xx = x + dirX[i];
            int yy = y + dirY[i];
            if (xx < 0 || yy < 0 || xx >= n || yy >= n || map[xx][yy] != 1) {
                continue;
            }
            if (map[xx][yy] == 1) {
                houseCount++;
                dfs(map, xx, yy);
            }
        }
    }
}

 

2667번: 단지번호붙이기