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

 

문제

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/49189

문제설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

풀이

BFS를 활용하여, 첫 노드(1)부터 순차척으로 나아가는데, 이때 Level개념을 두어서 멀리 떨어진 노드를 구분하였다.
일반적으로 while(!q.empty())안에 큐의 사이즈를 측정한 뒤, For문으로 그만큼 돌려서 level 구분.
추가적으로 큐에 중복되는 노드가 들어가지 않게 하기 위해, 큐에 삽입하면서 바로 노드의 방문여부까지 체크하였다.

이때 행렬로 구현한 경우, 속도가 빨랐으나 제한사항에 최대에 따르면 메모리가 어마어마하게 잡아먹혔다.
메모리 초과라고 안뜨고 그냥 실패라고 떠서 한참을 고민하다, 질문하기에 인접리스트로 구현해야 된다는 소식을 접하고
인접 리스트로구현하니 속도는 느려졌지만, 메모리가 적게 들었다.

아마 결정적인 차이는 큐에 노드를 추가할 때, 행렬일 경우 바로 간선이 있는지 확인할 수 있지만 (graph[current] [ a ] == 1)
리스트인 경우 graph.get(0).contains(a) 의 함수를 사용해야 해서 그런 것 같다.

시간 복잡도는, 행렬로 구현했을 경우 행렬에서 모든 노드를 방문하면서 검사하므로 $O(N^2)$
인접 리스트의 경우 모든 노드에서 그 간선만큼 방문하면서 검사하므로 $O(N+E)$이다.

 

코드(1) - 행렬

class Solution {
	int n;
	int [][] graph;
	
	
    public int solution(int n, int[][] edge) {
    	
    	this.n = n;
    	graph = new int[n][n];    	
    	makeVertex(edge);    	
        int answer = checkNode();
        return answer;
    }
    
    public void makeVertex(int[][] edge) {
    	for(int i=0; i<edge.length; i++) {
    		graph[edge[i][0]-1][edge[i][1]-1] = 1;
    		graph[edge[i][1]-1][edge[i][0]-1] = 1;
    	}
    }
    
    //BFS처럼 풀기
    public int checkNode() {
    	Queue<Integer> q = new LinkedList<Integer>();
    	int size = 0;
    	int current;
    	
    	//초기화
    	int [] hasVisited = new int[n];
    	for(int i=0;i < n ; i++) {
    		hasVisited[i] = 0;
    	}
    	  	
    	hasVisited[0] = 1;   	
		for(int a=0; a<n; a++) {
			if(hasVisited[a] == 0 && graph[0][a] == 1) {
				q.add(a);
				hasVisited[a] = 1;
			}
		}   
    	
    	while(!q.isEmpty()) {	
    		size = q.size();		 		
    		for(int i=0; i<size; i++) {   
    			System.out.println(q);
    			current = q.poll();   

        		for(int a=0; a<n; a++) {
        			if(hasVisited[a] != 1 && graph[current][a] == 1) {
        				q.add(a);
        				hasVisited[a] = 1;
        			}
        		}        		
    		}	  		
    	}
    	System.out.println("result : " + size);
    	return size;
    }
}

 

결과(1)

테스트 1 〉 통과 (0.92ms, 52.4MB)
테스트 2 〉 통과 (1.03ms, 52.1MB)
테스트 3 〉 통과 (0.94ms, 51.9MB)
테스트 4 〉 통과 (1.14ms, 52.6MB)
테스트 5 〉 통과 (11.90ms, 57.3MB)
테스트 6 〉 통과 (17.16ms, 59.5MB)
테스트 7 〉 통과 (772.03ms, 852MB)
테스트 8 〉 실패 (1541.39ms, 1.6GB)
테스트 9 〉 실패 (1076.14ms, 1.61GB)

 

코드(2) - 인접리스트

class Solution {
	int n;
	ArrayList<ArrayList<Integer>> graph;
    public int solution(int n, int[][] edge) {
    	
    	this.n = n;  	
    	makeVertex(edge);	
        int answer = checkNode();
        return answer;
    }
    
    public void makeVertex(int[][] edge) {
    	//그래프 구현
    	this.graph = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<n; i++) {
    		graph.add(new ArrayList<Integer>());
    	}
        //간선 추가
    	for(int i=0; i<edge.length; i++) {
    		graph.get(edge[i][0]-1).add(edge[i][1]-1);
    		graph.get(edge[i][1]-1).add(edge[i][0]-1);
    	}
    }
    
    //BFS처럼 풀기
    public int checkNode() {
    	Queue<Integer> q = new LinkedList<Integer>();
    	int size = 0;
    	int current;
    	
    	//초기화
    	int [] hasVisited = new int[n];
    	for(int i=0;i < n ; i++) {
    		hasVisited[i] = 0;
    	}  	
    	
    	hasVisited[0] = 1;
    	//만약 1에서 갈 수 있는게 1개도 없는 경우 0으로 끝
		for(int a=0; a<n; a++) {
			if(hasVisited[a] == 0 && graph.get(0).contains(a)) {
				q.add(a);
				hasVisited[a] = 1;
			}
		}   
  	
    	while(!q.isEmpty()) {	
    		size = q.size();		 		
    		for(int i=0; i<size; i++) {   
    			System.out.println(q);
    			current = q.poll();   
    			
        		for(int a=0; a<n; a++) {
        			if(hasVisited[a] != 1 && graph.get(current).contains(a)) {
        				q.add(a);
        				hasVisited[a] = 1;
        			}
        		}        		
    		}	  		
    	}
    	System.out.println("result : " + size);
    	return size;
    }
}

 

결과(2)

테스트 1 〉 통과 (1.12ms, 50.3MB)
테스트 2 〉 통과 (1.12ms, 52.9MB)
테스트 3 〉 통과 (1.32ms, 50.2MB)
테스트 4 〉 통과 (3.44ms, 52.4MB)
테스트 5 〉 통과 (55.83ms, 58MB)
테스트 6 〉 통과 (46.43ms, 59.6MB)
테스트 7 〉 통과 (773.81ms, 217MB)
테스트 8 〉 통과 (3614.70ms, 365MB)
테스트 9 〉 통과 (1770.15ms, 193MB)