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

문제 정보

---

 

2667번: 단지번호붙이기

 

핵심

---

DFS, 백 트래킹 알고리즘을 사용하여 풀이하는 문제

5<=N<=25 으로, 입력의 크기가 그렇게 크지 않으므로 다양한 풀이로 풀이할 수 있을것 같다

 

풀이

---

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

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sizeOfMap = Integer.parseInt(br.readLine());
        map = new int[sizeOfMap][sizeOfMap];
        visited = new boolean[sizeOfMap][sizeOfMap];
        List<Integer> countList = new ArrayList<>();

        for (int i = 0; i < sizeOfMap; i++) {
            String input = br.readLine();
            for (int j = 0; j < sizeOfMap; j++) {
                map[i][j] = Character.getNumericValue(input.charAt(j));
            }
        }
        for (int i = 0; i < sizeOfMap; i++) {
            for (int j = 0; j < sizeOfMap; j++) {
                count = 0;
                if (!visited[i][j] && map[i][j] != 0) {
                    dfs(i, j);
                    countList.add(count);
                }
            }
        }

        System.out.println(countList.size());
        Collections.sort(countList);
        for (int count : countList) {
            System.out.println(count);
        }
    }

    static void dfs(int row, int col) {
        if (!isValidPosition(row, col, map.length)) {
            return;
        }
        if (visited[row][col] || map[row][col] == 0) {
            return;
        }
        visited[row][col] = true;
        count++;
        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    }

    static boolean isValidPosition(int row, int col, int size) {
        return (row >= 0 && row < size && col >= 0 && col < size);
    }
}

NxN 배열에서 왼쪽 가장 위(0,0) 위치부터 오른쪽 가장 아래(N-1, N-1)까지 DFS를 통하여

인접한 위치로의 깊이 우선 탐색을 하여 지도의 값이 1이면 visited를 true로 만들어 주며, 해당 위치에서 다시 깊이 우선 탐색을 실시한다

한번 탐색할 때마다 count를 계속 올려주고, 계산이 끝났다면 이를 countList 리스트에 넣어 준다

마지막으로 이를 오름차순 정렬하기 위하여 Collections.sort() 를 사용하였다

 

고찰

---

.

 

Source Code on GitHub

---