[구름톤 챌린지 17일차] [Java] 통신망 분석

https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4

구름LEVEL

난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.

level.goorm.io

구름톤 알고리즘 챌린지?

이번엔 조금 재밌는 챌린지를 하게 되었습니다.

구름(구름 LEVEL) 에서 진행하는 구름톤 알고리즘 챌린지인데요.

조금 늦게 알게 되었지만 챌린지가 종료되기 전에라도 알게되어 다행입니다. 😀

이번 포스팅에서 다룰 문제는 챌린지 17일차 '통신망 분석' 입니다.

일반적인 DFS/BFS를 활용한 그래프 그룹화인줄 알았으나,

그룹화 + 정렬이라는 다소 특이한 문제였네요.

각각의 컴퓨터(노드)는 통신망(엣지)를 통해 연결되고,

통신망을 통해 서로 연결된 각 컴퓨터들은 컴포넌트(그룹)이라고 합니다.

그리고 각 컴포넌트를

1. 밀도 (엣지 개수 / 노드 개수)가 높은 순

2. 컴퓨터 수가 작은 순

3. 더 작은 컴퓨터를 가진 컴포넌트 순

으로 정렬했을때, 가장 위에 오는 컴포넌트(그룹)의 컴퓨터 개수를 오름차순으로 출력하는 문제였습니다.

전체 소스코드

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

public class Main {
    static class Group implements Comparable<Group> {
        int minNumOfNode;
        double computerCnt;
        double edgeCnt;

        public Group(int minNumOfNode, int computerCnt, int edgeCnt) {
            this.minNumOfNode = minNumOfNode;
            this.computerCnt = computerCnt;
            this.edgeCnt = edgeCnt;
        }

        @Override
        public int compareTo(Group o) {
            // 1. 밀집도가 높은 순
            double std1 = this.edgeCnt / this.computerCnt - o.edgeCnt / o.computerCnt;

            if (std1 < 0) return 1;
            else if (std1 > 0) return -1;
            else {
                // 2. 컴퓨터 수가 많은 순
                double std2 = this.computerCnt - o.computerCnt;
                if (std2 > 0) return 1;
                else if (std2 < 0) return -1;
                else {
                    // 3. 노드 번호가 작은 순
                    return this.minNumOfNode - o.minNumOfNode;
                }
            }
        }
    }

    static int n = 0;
    static int m = 0;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static ArrayList<Group> groups = new ArrayList<>();

    static int nowGroupSize = 0;
    static int nowMinNumOfNode = Integer.MAX_VALUE;
    static int nowEdgeSize = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            String[] input2 = br.readLine().split(" ");
            int a = Integer.parseInt(input2[0]);
            int b = Integer.parseInt(input2[1]);

            // 양방향 그래프
            graph[a].add(b);
            graph[b].add(a);
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                // 1번 컴퓨터부터 시작을 하므로 그룹 내 가장 작은 컴퓨터 개수는 탐색을 시작하는 컴퓨터의 번호임
                nowMinNumOfNode = i;
                nowGroupSize = 1;
                nowEdgeSize = 0;
                visited[i] = true;
                dfs(i);

                groups.add(new Group(nowMinNumOfNode, nowGroupSize, nowEdgeSize));
            }
        }

        Collections.sort(groups);

        ArrayList<Integer> ansList = new ArrayList<>();
        Arrays.fill(visited, false);

        visited[groups.get(0).minNumOfNode] = true;

        // 정렬 조건에 만족하는 그룹을 탐색
        finalDFS(groups.get(0).minNumOfNode, ansList);

        Collections.sort(ansList);

        StringBuilder sb = new StringBuilder();
        ansList.forEach(node -> sb.append(node).append(" "));

        System.out.println(sb.toString().trim());
    }

    static void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int currentNode = stack.pop();

            for (int connectedNode : graph[currentNode]) {
                // 이미 방문한 노드건, 방문하지 않은 노드건 간선의 개수를 증가시킴
                nowEdgeSize++;

                if (!visited[connectedNode]) {
                    // 방문하지 않은 노드라면 그룹의 크기를 증가시키고, 방문 처리를 함
                    nowGroupSize++;
                    visited[connectedNode] = true;
                    stack.push(connectedNode);
                }
            }
        }
    }

    static void finalDFS(int start, ArrayList<Integer> ansList) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        visited[start] = true;
        ansList.add(start);

        while (!stack.isEmpty()) {
            int currentNode = stack.pop();

            for (int node : graph[currentNode]) {
                if (!visited[node]) {
                    visited[node] = true;
                    stack.push(node);
                    ansList.add(node);
                }
            }
        }
    }
}

전체 소스코드입니다.

한 부분씩 같이 봅시다.

접근방법

1. DFS/BFS로 연결된 컴퓨터(노드)를 그룹화하고, 각 컴퓨터의 개수와 간선 개수를 저장

2. 정렬 조건에 맞게 정렬 후 가장 위에 오는 그룹을 찾기

3. 해당 그룹을 다시 DFS/BFS로 탐색하여 그룹 내 컴퓨터를 저장

각 노드를 그룹화하는건 일반적인 DFS/BFS를 사용한 그룹화와 크게 다르지 않습니다.

DFS/BFS를 사용한 그룹화를 잘 모르시겠다면 아래 포스팅과 문제를 참고해주세요.

https://uknowblog.tistory.com/32

[백준 2667번] [Kotlin] 단지번호붙이기

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지

uknowblog.tistory.com

Group 객체

static class Group implements Comparable<Group> {
    int minNumOfNode;
    double computerCnt;
    double edgeCnt;

    public Group(int minNumOfNode, int computerCnt, int edgeCnt) {
        this.minNumOfNode = minNumOfNode;
        this.computerCnt = computerCnt;
        this.edgeCnt = edgeCnt;
    }
}

저는 먼저 각 컴포넌트(그룹)에 관한 정보를 담을 Group 클래스를 정의하였습니다.

Group 클래스는 해당 컴포넌트(그룹)의 최소 번호 컴퓨터와 컴퓨터 개수, 통신선 개수를 담고 있습니다.

DFS 탐색

ArrayList<Group> groups = new ArrayList<>();

for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        // 1번 컴퓨터부터 시작을 하므로 그룹 내 가장 작은 컴퓨터 개수는 탐색을 시작하는 컴퓨터의 번호임
        nowMinNumOfNode = i;
        nowGroupSize = 1;
        nowEdgeSize = 0;
        visited[i] = true;
        dfs(i);

        groups.add(new Group(nowMinNumOfNode, nowGroupSize, nowEdgeSize));
    }
}

static void dfs(int start) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int currentNode = stack.pop();

        for (int connectedNode : graph[currentNode]) {
            // 이미 방문한 노드건, 방문하지 않은 노드건 간선의 개수를 증가시킴
            nowEdgeSize++;

            if (!visited[connectedNode]) {
                // 방문하지 않은 노드라면 그룹의 크기를 증가시키고, 방문 처리를 함
                nowGroupSize++;
                visited[connectedNode] = true;
                stack.push(connectedNode);
            }
        }
    }
}

저는 DFS를 재귀로 구현하였더니 런타임 에러가 발생하여,

혹시...? 하는 마음에 재귀 대신 스택으로 재구현하였더니 통과했습니다.

위 코드 블럭은 dfs로 컴포넌트를 그룹화하는 부분으로써,

1번부터 N번 컴퓨터까지 방문하지 않은 컴퓨터를 찾는다면 해당 컴퓨터를 기준으로 DFS 탐색을 진행합니다.

1번부터 차례로 탐색을 시작하므로, 각 컴포넌트의 가장 작은 컴퓨터 번호는 항상 시작 컴퓨터의 번호입니다.

또한, 첫 컴퓨터를 탐색할 경우 탐색한 컴퓨터 개수는 1개, 탐색한 간선은 0개이므로

dfs 탐색 시작 전에 nowGroupSize = 1, nowEdgeSize = 0 으로 지정합니다.

dfs 탐색을 진행하며 체크할 부분은 해당 컴포넌트를 이루고 있는 컴퓨터의 개수와 간선의 개수입니다.

앞서 말했듯, 가장 작은 컴퓨터의 번호는 항상 시작 컴퓨터의 번호이므로 신경쓰지 않아도 됩니다.

해당 컴퓨터와 연결된 컴퓨터를 차례로 탐색하며,

만약 방문하지 않은 컴퓨터라면 해당 컴퓨터를 stack에 넣고 방문체크 및 컴퓨터의 개수를 +1 한 뒤, dfs 탐색을 이어갑니다.

여기서 중요한 점은, 해당 컴퓨터를 이미 방문했건, 방문하지 않았건간에 Edge의 개수는 +1 해야 합니다.

컴포넌트를 이루고 있는 간선의 개수를 구하기 위함입니다.

한 컴포넌트에 대한 dfs 탐색이 끝난다면 Group 리스트에 넣고, 다음 컴포넌트를 탐색합니다.

컴포넌트(그룹) 정렬

static class Group implements Comparable<Group> {
    int minNumOfNode;
    double computerCnt;
    double edgeCnt;

    public Group(int minNumOfNode, int computerCnt, int edgeCnt) {
        this.minNumOfNode = minNumOfNode;
        this.computerCnt = computerCnt;
        this.edgeCnt = edgeCnt;
    }

    @Override
    public int compareTo(Group o) {
        // 1. 밀집도가 높은 순
        double std1 = this.edgeCnt / this.computerCnt - o.edgeCnt / o.computerCnt;

        if (std1 < 0) return 1;
        else if (std1 > 0) return -1;
        else {
            // 2. 컴퓨터 수가 많은 순
            double std2 = this.computerCnt - o.computerCnt;
            if (std2 > 0) return 1;
            else if (std2 < 0) return -1;
            else {
                // 3. 노드 번호가 작은 순
                return this.minNumOfNode - o.minNumOfNode;
            }
        }
    }
}

저는 Comparable 인터페이스와 compareTo 메소드를 사용하여 정렬 조건을 지정해줬습니다.

밀집도가 높은 순 -> 컴퓨터가 많은 순 -> 노드 번호가 작은 순입니다.

조건에 부합하는 컴포넌트를 찾기 위해 한 번 더 DFS 탐색 진행

static void finalDFS(int start, ArrayList<Integer> ansList) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    visited[start] = true;
    ansList.add(start);

    while (!stack.isEmpty()) {
        int currentNode = stack.pop();

        for (int node : graph[currentNode]) {
            if (!visited[node]) {
                visited[node] = true;
                stack.push(node);
                ansList.add(node);
            }
        }
    }
}

위 조건을 기준으로 정렬한 뒤, 가장 위에 오는 Group 객체의 시작 노드를 기준으로 한 번 더 DFS 탐색을 진행합니다.

저 같은 경우엔 ansList라는 ArrayList<Integer>를 사용해

해당 컴포넌트의 컴퓨터 번호를 넣어줬습니다.

답 출력

finalDFS(groups.get(0).minNumOfNode, ansList);

Collections.sort(ansList);

StringBuilder sb = new StringBuilder();
ansList.forEach(node -> sb.append(node).append(" "));

System.out.println(sb.toString().trim());

위 dfs 과정에서 컴포넌트 내 컴퓨터 번호를 얻었습니다.

컴포넌트 내 컴퓨터 번호를 오름차순으로 정렬해 출력하라 했으므로,

StringBuilder에 넣어 출력하였습니다.

마지막 공백 (" ")이 삽입되면 오답처리 되는 경우도 종종 겪었기에 trim()도 해줍시다.

후기

이와 비슷한 문제를 몇 번 풀었기에 아이디어 구상과 구현 자체는 빠르게 할 수 있었으나,

DFS를 재귀로 구현하는 바람에 런타임 에러를 겪어 조금 해맸던 문제였습니다.

DFS를 재귀로 구현하여 터진적은 처음이네요.

새로운 경험을 쌓은 것 같습니다.

저작자표시 변경금지

'코딩테스트 > Java' 카테고리의 다른 글

[백준 17106번] 빙고 (0)	2023.10.16
[백준 11654번] [Java] 아스키 코드 (0)	2023.02.05
[백준 15688번] [Java] 수 정렬하기 5 (0)	2023.02.01
[백준 10989번] [Java] 수 정렬하기 3 (0)	2023.02.01
[백준 2750번] [Java] 수 정렬하기 (0)	2023.02.01