[프로그래머스] 가장 먼 노드 / JAVA

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

그래프를 순회하며 가장 비용이 많이 소모된 그래프 노드의 갯수를 반환하는 문제이다.

 

Node 객체를 구현하여 한번 풀었고, 그래프를 나타내는 이중리스트를 통해 한번 풀어봤다.

 

> Solution (Node 객체 구현)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    private class Node{
        int val;

        ArrayList<Node> nextNodeList = new ArrayList<>();

        Node(int val){
            this.val = val;
        }
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Node> isTraveledSet = new HashSet<>();
        HashMap<Integer, Node> nodeMap = new HashMap<>();
        LinkedList<Node> nextNodeList = new LinkedList<>();

        for(int idx = 1; idx <= n; idx++){
            nodeMap.put(idx, new Node(idx));
        }

        for(int[] intArr : edge){
            nodeMap.get(intArr[0]).nextNodeList.add(nodeMap.get(intArr[1]));
            nodeMap.get(intArr[1]).nextNodeList.add(nodeMap.get(intArr[0]));
        }

        nextNodeList.add(nodeMap.get(1));
        isTraveledSet.add(nodeMap.get(1));

        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(Node node : nextNodeList.pollFirst().nextNodeList){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        return answer;
    }
}

> Result

 

> Solution (Graph를 나타내는 List)

import java.util.*;

class Solution{
    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Integer> isTraveledSet = new HashSet<>();
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        LinkedList<Integer> nextNodeList = new LinkedList<>();

        for(int[] intArr : edge){
            if(!graph.containsKey(intArr[0])){
                graph.put(intArr[0], new ArrayList<>());
            }
            if(!graph.containsKey(intArr[1])){
                graph.put(intArr[1], new ArrayList<>());
            }
            graph.get(intArr[0]).add(intArr[1]);
            graph.get(intArr[1]).add(intArr[0]);
        }
        
        nextNodeList.add(1);
        isTraveledSet.add(1);
        
        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(int node : graph.get(nextNodeList.pollFirst())){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        
        return answer;
    }
}

> Result

 

메모리 사용량과 같은 부분은 확실히 객체를 구현한 방식이 (아주약간)적게 사용되었다.

하지만 효율성에 있어서는 큰 차이를 보여주지 않는다.