[프로그래머스] 네트워크 - 자바

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

문제 풀이

그래프 문제로 union-find를 통해 부모노드를 설정하고 각 노드마다 같은 부모인지를 체크하여 같은 네트워크인지 체크할 수 있다.

하지만 위와 같인 로직을 적용시키기 위해 부모노드로 승격시키는 로직과 각 노드마다 부모노드로 거슬러 올라가야 되는 알고리즘을 모두 구현해야 해서 불편하다

 

더 간단한 방법으로 각 노드마다 연결된 간선이 있으면 네트워크를 증가시키고 해당 노드와 연결된 모든 노드를 제거한다.

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    static List[] nodes;
    static int answer = 0;

    public int solution(int n, int[][] computers) {
        int len = computers.length;

        nodes = new List[len];
        for (int i = 0; i < len; i++) {
            nodes[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (computers[i][j] == 1) {
                    nodes[i].add(j);
                }
            }
        }

        for (int i = 0; i < len; i++) {
            bfs(i);
        }

        return answer;
    }

    static void bfs(int n) {
        if (nodes[n].size() == 0)
            return;
        answer++;

        LinkedList<Integer> q = new LinkedList<>();
        q.offer(n);

        while (!q.isEmpty()) {
            Integer now = q.poll();
            for (int i = 0; i < nodes[now].size(); i++) {
                q.offer((Integer) nodes[now].get(i));
            }
            nodes[now].clear();
        }

    }
    
}

코드 풀이

예제는 노드가 1부터 시작하지만 각 노드별 번호는 영향을 주지 않아 더 간단하게 0부터 시작하도록 구현

bfs를 통해 연결된 모든 간선 제거