문제 요약
정점 개수 n과 간선 정보 edge가 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제다.
거리의 기준은 “간선 개수(=이동 횟수)”이고, 연결 그래프라는 전제에서 BFS로 최단거리를 구하면 된다.
핵심 아이디어 1 (BFS)
이 문제는 “모든 간선의 비용이 동일(1)”인 그래프에서 1번 노드로부터의 최단거리를 전부 구한 뒤, 그 중 최댓값을 찾는 문제다.
BFS는 레벨 순서대로 확장되기 때문에, distance[x]를 “처음 채우는 순간”이 곧 1번에서 x번까지의 최단거리로 확정된다.
즉 흐름은:
1) BFS로 distance[] 채우기
2) distance[]에서 최대값 찾기
3) 최대값과 같은 노드 개수 세기
핵심 아이디어 2 (인접 리스트 + 정렬)
그래프 입력은 간선 목록(쌍)으로 들어오지만, BFS는 “현재 노드에서 갈 수 있는 다음 노드들”을 빠르게 꺼내야 해서 인접 리스트가 유리하다.
또한 이 문제는 “방문 순서” 자체가 답에 영향을 주진 않지만, 인접 리스트를 정렬해두면 디버깅할 때 탐색 순서가 고정되어 확인이 편하다.
입력 처리 & 인접 리스트 구성
adjList를n+1크기로 만든다(노드 번호가 1부터라 0은 더미).- 간선 정보를 양방향으로 추가한다(무방향 그래프).
- (선택) 각 리스트를 오름차순 정렬한다.
for (int i = 0; i < n + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < edge.length; i++) {
int nodeA = edge[i][0];
int nodeB = edge[i][1];
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}BFS 구현(거리 배열 distance[])
distance 배열을 visited처럼 쓰기
여기서는 visited[] 대신 distance[]를 -1로 초기화해서 “아직 방문 안 함”을 표현한다.
distance[x] == -1: 아직 미방문distance[x] >= 0: 방문 완료 + 최단거리 확정
int[] distance = new int[n + 1];
Arrays.fill(distance, -1);
Queue<Integer> q = new LinkedList<>();
q.add(1);
distance[1] = 0;BFS 핵심 로직
while (!q.isEmpty()) {
int current = q.poll();
for (int next : adjList.get(current)) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
q.add(next);
}
}
}포인트:
distance[next]를 “큐에 넣는 순간” 채워서 중복 삽입을 막는다.- 한 번 채워진
distance[next]는 BFS 특성상 최단거리로 확정된다.
정답 계산(가장 먼 노드 개수)
BFS가 끝나면 distance[]에는 1번으로부터의 거리들이 저장되어 있다.
1) 최댓값 maxDistance 찾기
2) distance[i] == maxDistance인 노드 개수 세기
int maxDistance = -1;
for (int i = 1; i <= n; i++) {
maxDistance = Math.max(maxDistance, distance[i]);
}
int answer = 0;
for (int i = 1; i <= n; i++) {
if (distance[i] == maxDistance) answer++;
}전체 코드(제출용)
import java.util.*;
class Solution {
static List<List<Integer>> adjList = new ArrayList<>();
public int solution(int n, int[][] edge) {
// 인접 리스트 생성
adjList.clear();
for (int i = 0; i < n + 1; i++) {
adjList.add(new ArrayList<>());
}
// 무방향 그래프
for (int i = 0; i < edge.length; i++) {
int nodeA = edge[i][0];
int nodeB = edge[i][1];
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
// (선택) 정렬
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}
// 1번에서 BFS
int[] distance = bfs(n);
// 최댓값 & 개수
int maxDistance = -1;
for (int i = 1; i <= n; i++) {
maxDistance = Math.max(maxDistance, distance[i]);
}
int answer = 0;
for (int i = 1; i <= n; i++) {
if (distance[i] == maxDistance) answer++;
}
return answer;
}
public static int[] bfs(int n) {
int[] distance = new int[n + 1];
Arrays.fill(distance, -1);
Queue<Integer> q = new LinkedList<>();
q.add(1);
distance[1] = 0;
while (!q.isEmpty()) {
int current = q.poll();
for (int next : adjList.get(current)) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
q.add(next);
}
}
}
return distance;
}
}
Eazy하게