[Programmers] 가장 먼 노드 Java

문제 링크

https://school.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번 노드 사이에 간선이 있다는 의미입니다.

 

입출력 예

입출력 예 설명
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

 

풀이

int 이차원 배열을 ArrayList 이차원 배열로 바꾼다.

 

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for(int i = 0; i <= n; i++) graph.add(new ArrayList<>());

 

graph를 선언 후 초기화해준다. 노드의 숫자에 해당하는 index에 인접하는 노드의 숫자를 넣기 위해 for문을 0부터 n까지 돌렸다. 밑의 코드에서  index 0은 비워두고 index 1부터 index n까지 들어가게 된다. 초기화 후 각 배열에는 []가 들어가있다.

 

 

        for(int[] i : edge) {
        	graph.get(i[0]).add(i[1]); // 맨 처음 실행 시 get은 [] 반환. 빈 배열에 add하게 됨.
        	graph.get(i[1]).add(i[0]);
        }

 

 

 

        for(int i = 0; i < graph.size(); i++) {
        	System.out.println(graph.get(i));
        }

edge에 입출력 예를 넣고 graph를 출력해보면 노드의 숫자에 해당하는 index에 인접하는 노드의 숫자가 나오는 것을 볼 수 있다.

 

index 0 : []

index 1 :  [3, 2] 

index 2 :  [3, 1, 4, 5]

index 3 :  [6, 4, 2, 1]

index 4 :  [3, 2]

index 5 :  [2]

index 6 :  [3]

 

 

 

이제 방문 여부를 체크할 visit 배열을 만들고 graph, n, visit을 파라미터로 넘긴 bfs 메서드를 리턴한다.

 

bfs 구현

Queue 선언 후 시작 노드 1, depth 0인 값을 추가한다.(초기화)

시작 노드 1의 방문 여부를 true로 바꾸고 queue가 비어있지 않을 때까지 while문으로 반복한다.

 

while문 Pseudo-code

while(queue가 비어있지 않을 때까지)
    queue에서 하나를 꺼낸다.
    int v = 배열의 첫 번째 요소 // 노드
    int depth = 배열의 두 번째 요소 // 깊이
    
    만약 depth가 최대 depth라면 answer 증가
    만약 지금까지 최대 depth보다 depth가 더크면
    	최대 depth 값 갱신
        answer = 1 // 초기화
    
    v에 해당하는 노드의 인접 노드들을 모두 탐색해본다.
    	int w = get() // 인접 노드
        
        만약 w가 아직 방문하지 않은 노드라면(새로운 노드 발견)
        	queue에 (w, 현재 depth에 +1)를 넣는다.
            방문 여부를 true로 변경한다.

모든 while문이 종료되면(queue가 비어있음. 모두 탐색함.) answer를 return한다.

 

 

 

코드

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

class Solution {
	ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	
    public int solution(int n, int[][] edge) {
    	// graph와 visited는 배열의 크기가 n + 1이다.
        for(int i = 0; i <= n; i++) graph.add(new ArrayList<>()); // []이 들어가 있음.
                
        for(int[] i : edge) {
        	graph.get(i[0]).add(i[1]); // 맨 처음 실행 시 get은 [] 반환. 빈 배열에 add 하게 됨.
        	graph.get(i[1]).add(i[0]);
        }
        
        /*
        for(int i = 0; i < graph.size(); i++) {
        	System.out.println(graph.get(i));
        }
        */
                
        boolean[] visit = new boolean[n + 1];
		
        return bfs(graph, n, visit);
    }
    
    public static int bfs(ArrayList<ArrayList<Integer>> graph, int n, boolean[] visit) {
    	Queue<int[]> queue = new LinkedList<>();
    	int answer = 0;
    	
    	queue.add(new int[] {1, 0});
    	visit[1] = true;
    	int maxDepth = 0;
    	
    	while(!queue.isEmpty()) {
    		int[] arr = queue.poll();
    		int v = arr[0];
    		int depth = arr[1];
    		
    		if(maxDepth == depth) answer++;
    		else if(maxDepth < depth) {
    			maxDepth = depth;
    			answer = 1;
    		}
    		
    		for(int i = 0; i < graph.get(v).size(); i++) {
    			int w = graph.get(v).get(i); // 인접 정점
    			
    			if(!visit[w]) {
    				queue.add(new int[] {w, depth + 1});
    				visit[w] = true;
    				}
    			}
    		}
    	return answer;    	
    }
    
    public static void main(String[] args) {
    	Solution s = new Solution();
    	int n = 6;
    	int[][] edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
    	
    	System.out.println(s.solution(n, edge));
	}
}