[프로그래머스][Java][Lv. 3] 네트워크

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    int answer = 0;
    HashMap<Integer, Node> nodeMap = new HashMap<>();
    ArrayList<Node> closedList = new ArrayList<>();
    
    public int solution(int n, int[][] computers) {
        for (int i = 0; i < computers.length; i++) {
            nodeMap.put(i, new Node());
        }
        
        for (int i = 0; i < computers.length; i++) {
            nodeMap.get(i).setconnectedList(i, computers[i]);
        }
        
        for (int i = 0; i < computers.length; i++) {
            if (!closedList.contains(nodeMap.get(i))) {
                doDfs(nodeMap.get(i));
                answer++;
            }
        }
        return answer;
    }
    
    public void doDfs(Node node) {
        closedList.add(node);
        
        for (Node n : node.getConnectedList()) {
            if (!closedList.contains(n)) {
                doDfs(n);
            }
        }
    }
    
    class Node {
        ArrayList<Node> connectedList = new ArrayList<>();
        
        public void setconnectedList(int currentComputer, int[] computerArr) {
            for (int i = 0; i < computerArr.length; i++) {
                if (i != currentComputer && computerArr[i] == 1) {
                    connectedList.add(nodeMap.get(i));
                }
            }
        }
        
        public ArrayList<Node> getConnectedList() {
            return connectedList;
        }
    }
}

 

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int nodeSize = computers.length;
        ArrayList<Integer>[] nodes = new ArrayList[computers.length];
        boolean[] visited = new boolean[nodeSize];
        
        for (int i = 0; i < nodeSize; i++) {
            nodes[i] = new ArrayList<>();
            
            for (int j = 0; j < nodeSize; j++)  {
                if (i == j) continue;
                if (computers[i][j] == 1) nodes[i].add(j);
            }
        }
        
        for (int i = 0; i < nodeSize; i++) {            
            if (visited[i]) continue;
            else {
                Queue<Integer> nodeQ = new LinkedList<>();
                nodeQ.add(i);
                visited[i] = true;
                
                while (!nodeQ.isEmpty()) {
                    Integer node = nodeQ.poll();
                    
                    for (Integer linkedNode : nodes[node]) {
                        if (!visited[linkedNode]) {
                            nodeQ.add(linkedNode);
                            visited[linkedNode] = true;
                        }
                    }
                }
            }
            answer++;
        }
        return answer;
    }
}

ㄴ 2024. 12. 27. 2차 풀이

 

 

---

후기

그냥 단순히 노드를 생성하고, 연결되어 있는 노드는 연결시킨 뒤, 노드들을 순회하면서 연결되어 있는 노드는 모두 closedList에 넣고 이건 네트워크 1개인 것으로 설정한다. 아무것도 연결되어 있지 않은 노드는 당연히 네트워크 1개로 생각하면 된다. closedList에 이미 있는 노드는 연결되어 있어서 어딘가의 노드에서 이미 센 노드이거나 연결되지 않은 노드이므로 처리하지 않고 다음 노드로 넘어간다.