[코딩테스트] Java 가장 먼 노드

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

bfs 탐색을 통해 1번 노드에서 가장 먼 노드를 찾는 문제였습니다. 저는 visited 배열과 step 배열을 통해서 문제를 풀었습니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited;
    int[] step;
    List<List<Integer>> graph = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>();
    
    public void bfs() {
        while(!q.isEmpty()) {
            int src = q.poll();
            for(int desc: graph.get(src)) {
                if (!visited[desc]) {
                    visited[desc] = true;
                    step[desc] = step[src] + 1;
                    q.add(desc);
                }
            }
        }
    }
    
    public void init(int n) {
        visited = new boolean[n + 1];
        step = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        q.add(1);
        visited[1] = true;
        step[1] = 1;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 1;
        
        init(n);
        
        for(int[] vertex: edge) {
            int src = vertex[0];
            int desc = vertex[1];
            graph.get(src).add(desc);
            graph.get(desc).add(src);
        }
        
        bfs();
        
        Arrays.sort(step);
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if (max < step[i]) {
                answer = 1;
                max = Math.max(max, step[i]);
            } else if (max == step[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  
  • boolean[] visited
    해당 인덱스의 노드를 방문했는지 확인하는 배열입니다.
  • int[] step
    해당 인덱스의 노드의 그래프의 깊이 입니다.
  • List<List<Integer>> graph = new ArrayList<>()
    src와 desc로 설정하여 graph를 설정합니다.
  • Queue<Integer> q = new LinkedList<>()
    bfs 를 위한 Queue를 선언합니다.
• bfs 메소드
  일반 bfs 메소드입니다.
  • src와 desc를 선언하여 방문하지 않은 desc면 q에 넣고 step도 초기화합니다.
• init 메소드
  변수들을 초기화하는 메소드입니다.

Arrays.sort(step);
int max = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
    if (max < step[i]) {
        answer = 1;
        max = Math.max(max, step[i]);
    } else if (max == step[i]) {
        answer++;
    }
}

return answer;

• 몇번 인덱스를 찾는 문제가 아니라 가장 먼 노드의 갯수를 구하는 문제이므로 Array를 정렬합니다.
• step이 가장 큰 노드를 찾으면 answer를 초기화 합니다.
• max와 step[i]가 같으면 answer을 1 증가합니다.
• 반복문 종료 후 answer를 반환합니다.