[DFS/자바] 코드트리 IL. 마을 구분하기 (2회독)

지난 실력진단 문제에서 구성되는 마을의 최대 크기라던지, 마을의 개수를 어떻게 구할 수 있을지 쉽게 떠오르지 않았어서 해당 부분을 연습하기 위해 이 문제를 다시 풀어봤다.

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

접근

이 문제는 단순 반복문을 통해서는 나의 한계로 로직이 떠오르지도 않거니와, 있더라도 분명히 매우 복잡할 것이므로 패스하였다.

 

그 외에 순열, 조합과 같은 경우의 수를 탐색하는 경우도 아니고, 최대최소를 얻는 그리디한 바이브의 문제도 아니였다.

 

탐색 알고리즘 중에 이웃한 항과의 관계를 통해 답을 도출해 내는 그래프 알고리즘이 이 문제에 적합하다 판단했고, DFS를 통해 이 문제를 다시 풀어보았다. (이론상 생각해보면 BFS()로 해도 전혀 문제될 것은 없으나, DFS의 로직이 더욱 간결하므로, DFS가 가능하다면 DFS로 접근하는 것이 효율적이라 판단하였다.)

 

구현

마을의 크기는 dfs() 함수와 main 함수에서도 쓰일 예정이라 전역변수 int cnt로 선언하여 계산해 주었고, 계산된 마을의 크기는 dfs를 마친 이후 리스트에 저장하여 차례대로 출력해 주었다. 마을의 크기는 리스트의 크기로 대체하였다.

 

마을의 크기를 오름차순으로 나열해줘야 하므로, 처음에는 마을의 크기들을 트리셋을 이용하여 작업해 주었다. 하지만 이는 마을의 크기가 동일하면 중복이 제거되어 정답을 맞출 수 없었다. 따라서 자료구조를 리스트로 바꾼 뒤, 오름차순으로 정렬하여 출력해 주었다.

 

로직

package 코드트리.그래프.DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 마을_구분하기_2회차 {
    private static int n;
    private static int[][] arr;
    private static boolean[][] visited;
    private static int cnt = 1;
    private static List<Integer> li = new ArrayList<>();
    private static Queue<Pair> q = new LinkedList<>();
    private static Queue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        /*
        * 인접한 사람들은 같은 마을
        *
        * 총 마을의 개수와, 같은 마을에 있는 사람의 수를 오름차순으로 정렬하여 출력
        * */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) {
                    q.add(new Pair(i, j));
                }
                arr[i][j] = num;
            }
        }
        for (Pair p : q) {
            if (canGo(p.y, p.x)) {
                visited[p.y][p.x] = true;
                dfs(p);
                li.add(cnt);
                cnt = 1;
            }
        }
        System.out.println(li.size());
        li.sort(Comparator.naturalOrder());

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

    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x) {
        return inRange(y,x) && arr[y][x] == 1 && !visited[y][x];
    }

    private static void dfs(Pair p) {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            int newY = p.y + dy[i];
            int newX = p.x + dx[i];
            if (canGo(newY, newX)) {
                visited[newY][newX] = true;
                cnt++;
                dfs(new Pair(newY, newX));
            }
        }
    }

    private static class Pair {
        private int x, y;

        private Pair(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }
}

 

비교

2회차였으니, 지난 번 나의 풀이와 이번 풀이를 비교해보겠다. 주요 로직만 발췌하였다.

public class 마을_구분하기 {
		// ... 입력 ...
        
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (grid[j][k] == 1) {
                    grid[j][k] = 0;
                    TreeSet<Integer> ts = new TreeSet<>();
                    ts.add(0);
                    visited[j][k] = 1;
                    DFS(j, k, ts);
                    pq.add(ts.last());
                }
            }
        }
        
        int size = pq.size();
        System.out.println(size);
        for (int i = 0; i < size; i++) {
            System.out.println(pq.poll() + 1);
        }
    }

    public static void DFS(int r, int c, TreeSet<Integer> ts) {
        for (int i = 0; i < 4; i++) {
            int newRow = r + dr[i];
            int newColumn = c + dc[i];
            if (canGo(newRow, newColumn)) {
                ts.add(ts.last() + 1);
                grid[newRow][newColumn] = 0;
                visited[newRow][newColumn] = 1;
                DFS(newRow, newColumn, ts);
            }
        }
    }

	// ... inRange, canGo 선언 ...

}

2회차 때에 static int cnt로 사용하던 역할을, 여기서는 treeSet을 main에서 선언한 뒤, 이를 dfs 함수의 파라미터에 주소값으로 넘겨서 마을의 크기를 카운트 한 뒤에 그 최종 크기를 우선순위 큐에 저장하는 방식을 택했다.

 

개인적으로 결과값을 우선순위 큐에 담아서 minheap의 특성을 잘 활용한 점은 첫번째 풀이에서 잘 한 점이라고 생각한다. 새로운 자료구조를 배운지 얼마 안됐어서 이런 부분을 적극적으로 활용했던 것 같은데, minheap과 같은 특징들을 잘 이해하고 적절하게 사용했던 모습으로 보여 다시금 반성하게 된다.

 

하지만 visited를 별도로 운영하면서도 grid를 굳이 변경하는 로직도 별로고, 굳이 treeset을 이용하여 단일 값을 갱신했던 로직은 매우 불필요해 보인다. 이러한 면에서는 현재 로직이 조금 더 깔끔하다고 느껴진다.

 

대체적으로는 지금의 내가 조금 더 나은 구성을 보이는 것 같아 다행이면서도, 과거의 내가 잘 구사하던 것을 계속 까먹는다는 것도 이해하는 시간이었다. 역시 무엇이든 꾸준함이 진리다.