[49189] 가장 먼 노드

✔ 가장 먼 노드

[프로그래머스 49189]

문제 분석하기

가중치가 없는 인접 리스트로 그래프를 표현한 후, BFS 탐색을 수행하며 가장 먼 거리를 저장

이후 가장 먼 거리를 가지고 노드의 개수를 찾음

손으로 풀어보기

1. 인접 리스트로 노드와 간선의 그래프를 표현
2. BFS 탐색 알고리즘으로 탐색을 수행하면서 각 노드로 가는 거리값을 방문 배열에 저장
   • 이때 가장 먼 거리를 저장
3. 탐색 종료 후 방문 배열에 값이 가장 먼 거리와 같다면 갯수 증가
4. 노드의 개수 반환 

슈도코드 작성하기

n(노드의 개수)
edge(간선의 정보가 담긴 2차원 배열)
answer(가장 멀리 떨어진 노드의 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 거리 저장 배열)
depth(가장 먼 거리)
for(n만큼 반복하기) {
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(edge.length만큼 반복하기) {
    A 인접 리스트에 그래프 데이터 저장하기
}
visited 배열 초기화하기
depth 초기화하기
BFS(X) 실행하기
for(n만큼 반복하기) {
    방문 거리가 depth인 노드가 있다면 answer 증가
}
answer 리턴

BFS {
    큐 자료구조에 출발 노드 더하기(add 연산)
    visited 배열에 현재 노드 방문 기록하기
    while(큐가 빌 때까지) {
        큐에서 노드 데이터를 가져오기(poll 연산)
        현재 노드의 연결 노드 중 방문하지 않은 노드로
        이전 노드의 방문 노드 거리 + 1
        depth 갱신
        큐에 데이터 삽입(add 연산)
    }
}

코드 구현하기

/**
 * 49189) 가장_먼_노드
 */
public class K001_49189 {
    // A(그래프 데이터 저장 인접 리스트)
    static ArrayList<Integer>[] A;
    // visited(방문 거리 저장 배열)
    static int visited[];
    // depth(가장 먼 거리)
    static int depth;

    // n(노드의 개수)
    // edge(간선의 정보가 담긴 2차원 배열)
    public int solution(int n, int[][] edge) {
        // A 인접 리스트의 각 ArrayList 초기화하기
        A = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            A[i] = new ArrayList<Integer>();
        }
        // A 인접 리스트에 그래프 데이터 저장하기
        for (int i = 0; i < edge.length; i++) {
            A[edge[i][0]].add(edge[i][1]);
            A[edge[i][1]].add(edge[i][0]);
        }
        // visited 배열 초기화하기
        visited = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            visited[i] = -1;
        }
        // depth 초기화하기
        depth = 1;
        // BFS(X) 실행하기
        BFS(1);
        // answer(가장 멀리 떨어진 노드의 개수)
        int answer = 0;
        // 방문 거리가 depth인 노드가 있다면 answer 증가
        for (int i = 0; i <= n; i++) {
            if (visited[i] == depth) {
                answer += 1;
            }
        }
        // answer 리턴
        return answer;
    }

    // BFS
    private void BFS(int Node) {
        // 큐 자료구조에 출발 노드 더하기(add 연산)
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        // visited 배열에 현재 노드 방문 기록하기
        visited[Node]++;
        while (!queue.isEmpty()) {
            // 큐에서 노드 데이터를 가져오기(poll 연산)
            int now = queue.poll();
            // 현재 노드의 연결 노드 중 방문하지 않은 노드로
            for (int i : A[now]) {
                if (visited[i] == -1) {
                    // 이전 노드의 방문 노드 거리 + 1
                    visited[i] = visited[now] + 1;
                    // depth 갱신
                    depth = Math.max(depth, visited[i]);
                    // 큐에 데이터 삽입(add 연산)
                    queue.add(i);
                }
            }
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_49189 solution = new K001_49189();

        int n = 6;
        int[][] edge = { { 3, 6 }, { 4, 3 }, { 3, 2 }, { 1, 3 }, { 1, 2 }, { 2, 4 }, { 5, 2 } };

        int result = solution.solution(n, edge);

        System.out.println(result);
    }
}