[programmers] 가장 먼 노드

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

프로그래머스

 

---

< 가장 먼 노드 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int solution(int n, int[][] edge) {
		int answer = 0;

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

		for (int i = 0; i < n + 1; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < edge.length; i++) {
			list.get(edge[i][0]).add(edge[i][1]);
			list.get(edge[i][1]).add(edge[i][0]);
		}

		int depth[] = new int[n + 1];

		bfs(list, depth);

		int max = 0;
		for (int i = 1; i < n + 1; i++) {
			if (max < depth[i]) {
				max = depth[i];
				answer = 1;
			} else if (max == depth[i]) {
				answer += 1;
			}
		}

		return answer;
	}

	private void bfs(ArrayList<ArrayList<Integer>> list, int[] depth) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);

		boolean visited[] = new boolean[list.size()];
		visited[1] = true;

		while (!queue.isEmpty()) {
			int num = queue.poll();

			for (int temp : list.get(num)) {
				if (!visited[temp]) {
					visited[temp] = true;
					depth[temp] = depth[num] + 1;
					queue.add(temp);
				}
			}
		}
	}
}

 

ArrayList에 간선을 양방향으로 저장한다. bfs를 호출한 뒤 depth를 살펴보며 가장 멀리 떨어진 노드의 개수를 구한다.

 

bfs 함수에서는 Queue에 시작 노드인 1을 저장하고 방문 표시를 한 뒤 Queue가 빌 때까지 다음 과정을 반복한다. 

1. queue poll

2. 현재 노드와 연결된 노드를 살펴보며 아직 방문하지 않은 노드라면 방문 표시, 떨어진 간선 개수를 업데이트 한 뒤 queue에 저장한다.

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges