소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 프로그래머스 - 가장 먼 노드 (문제 링크)
- BFS(너비 우선 탐색)
- 그래프 탐색
- 최단 경로
문제 설명
주어진 n개의 노드로 이루어진 그래프에서, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제입니다. 가장 멀리 떨어진 노드란, 1번 노드에서 출발하여 최단 경로로 도달했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며, 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열의 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
예제 1
n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
Output: 3
예제 설명
위의 예제에서, 1번 노드에서 가장 멀리 떨어진 노드는 6번, 4번, 5번 노드이며, 이들은 모두 4개의 간선을 통해서만 도달할 수 있습니다. 따라서 가장 멀리 떨어진 노드의 개수는 3개입니다.
문제 접근
이 문제는 그래프 탐색 문제로, BFS(너비 우선 탐색)을 이용해 1번 노드로부터 모든 노드까지의 최단 거리를 계산한 뒤, 가장 멀리 있는 노드의 개수를 찾는 방식으로 접근할 수 있습니다.
- 그래프 초기화
- 주어진 간선 정보를 바탕으로 그래프를 인접 리스트 형태로 초기화합니다.
- BFS 탐색
- 1번 노드부터 시작하여 BFS를 이용해 각 노드까지의 최단 거리를 계산합니다.
- 각 노드까지의 거리를 depth로 저장하고, 방문한 노드는 다시 방문하지 않도록 visited 배열을 사용합니다.
- 최대 거리 계산 및 결과 반환
- BFS 탐색이 완료된 후, 최대로 멀리 떨어진 노드의 거리를 계산하고, 그 거리를 가지는 노드의 개수를 셉니다.
풀이 - Java 코드
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
class Solution {
private boolean[] visited;
private int answer, depth;
private ArrayList<Node>[] graph;
private ArrayList<Node> resultList;
private Queue<Node> queue;
public int solution(int n, int[][] edge) {
depth = 0;
queue = new ArrayDeque<>(n);
graph = new ArrayList[n + 1];
visited = new boolean[n + 1];
// 그래프 초기화
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
// 간선 정보 추가
for (int i = 0; i < edge.length; i++) {
int start = edge[i][0];
int end = edge[i][1];
graph[start].add(new Node(end, -1));
graph[end].add(new Node(start, -1));
}
// BFS 탐색 시작
bfs();
// 최대 거리 노드 개수 계산
resultList.forEach(
node -> {
if (node.depth == depth) {
answer++;
}
}
);
return answer;
}
private void bfs() {
ArrayList<Node> nodes = graph[1];
visited[1] = true;
resultList = new ArrayList<>();
resultList.add(new Node(1, 0));
// 1번 노드에서 연결된 노드들 큐에 추가
for (Node node : nodes) {
resultList.add(node);
node.depth = 1;
queue.add(node);
visited[node.end] = true;
}
// BFS 진행
while (!queue.isEmpty()) {
Node node = queue.poll();
if (depth < node.depth) {
depth = node.depth;
}
for (Node n : graph[node.end]) {
if (!visited[n.end]) {
n.depth = node.depth + 1;
queue.add(n);
resultList.add(n);
visited[n.end] = true;
}
}
}
}
}
class Node {
int end;
int depth;
public Node(int end, int depth) {
this.end = end;
this.depth = depth;
}
}풀이 설명
- 그래프 초기화
- 주어진 간선 정보를 기반으로 각 노드에 연결된 노드들을 인접 리스트 형태로 저장합니다.
- BFS 탐색
- 1번 노드에서 시작하여 연결된 모든 노드를 BFS 방식으로 탐색합니다.
- 각 노드까지의 거리를 depth로 계산하고, 큐를 사용해 다음에 탐색할 노드를 관리합니다.
- 최대 거리 계산 및 결과 반환
- BFS 탐색을 마친 후, 최대 depth를 가지는 노드의 개수를 계산하여 반환합니다.
마무리하며
- 이번 문제를 통해 BFS를 활용한 그래프 탐색 방법을 다시 한 번 복습할 수 있었습니다.
- 그래프에서 최대 depth를 찾는 문제에 대해, BFS로 최단 거리를 구한 뒤, 최대 depth를 가지는 노드의 개수를 계산하여 문제를 해결했습니다.
반응형
