[Java] 백준 단지번호붙이기

1. 문제분석

기본적인 DFS 문제다. 나는 visited배열 + 재귀형식으로 구현을 했다.

단지별로 모여있다는 것은 출발점에서 DFS를 통해 탐색이 가능한 경우를 1개로 친다.

예시인 1단지를 보자. 만약 방문이 가능하다면 DFS를 실행한다. 그렇다면 해당 구역을 전부 찾았을 것 이다.

찾은 구역의 visited값을 false로 두고 다음 탐색 가능 구역을 가면 된다.

 

탐색이 가능하면 단지의 개수를 증가하고 ArrayList에 넣어주었다.

마지막 단지개수와 오름차순으로 정렬한 단지 값을 출력하면 된다.

2. 구현

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

public class Main {

    //단지 지도
    static int[][] arr;
    //방문했는지 안했는지 구분
    static boolean[][] visited;
    //델타 탐색을 위한 값(하, 상, 우, 좌)
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    //단지의 크기(size * size)
    static int size;
    //단지의 개수
    static int count = 1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());
        arr = new int[size][size];
        visited = new boolean[size][size];
        for (int i = 0; i < size; i++) {
            String data = br.readLine();
            for (int j = 0; j < size; j++) {
                arr[i][j] = data.charAt(j) - '0';
            }
        }

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

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                //방문을 아직 안했고 단지라면?
                if (!visited[i][j] && arr[i][j] == 1) {
                    //이미 1개는 된 상태므로 1로 초기화
                    count = 1;
                    dfs(i, j);
                    //나온 값을 list에 추가
                    list.add(count);
                }
            }
        }
        //오름차순 정렬
        Collections.sort(list);
        System.out.println(list.size());
        for (int a : list) {
            System.out.println(a);
        }
    }

    static boolean check(int x, int y) {
        //델타 탐색으로 가져온 x,y값이 조건에 맞는지?
        if (x < 0 || x >= size) return false;
        if (y < 0 || y >= size) return false;
        return !visited[x][y];
    }

    static void dfs(int x, int y) {
        //x, y는 방문한 것으로 처리
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            //델타 탐색
            int moveX = x + dx[i];
            int moveY = y + dy[i];

            //check 조건에 맞으면서 단지인지?
            if (check(moveX, moveY) && arr[moveX][moveY] == 1) {
                dfs(moveX,moveY);
                //탐색했으므로 1추가
                count++;
            }
        }
    }
}

DFS를 해봤다면 쉽게 풀 수 있는 문제다.

나는 check를 통해 범위와 방문여부를 return 해주었다.

3. 마무리

왜 그랬는지 모르겠는데 SET을 써서 중복을 없애고 어쩌고..를  구현할려다보니 시간이 걸렸다.

단순하게 생각하면 좋을텐데..