오늘의 키워드
•
트리의 지름
•
BFS
•
거리 누적
•
long 자료형 처리
문제 파악 및 풀이
•
트리 형태의 연결 구조에서, 가장 먼 방 사이의 거리를 구하는 문제다.
•
시작점이 고정(0번 방)이고, 모든 경로가 양방향으로 주어지며 사이클이 없기 때문에 BFS로 거리 누적이 가능하다고 판단했다.
•
BFS를 통해 각 방까지의 누적 거리(memo 배열)를 계산한 뒤, 그 중 최대 값을 출력하면 된다.
•
하지만 가중치 C의 범위를 1,000,000,000까지 주는 것을 처음에 간과해서 int로 처리했다가 오버플로우 위험이 생겼고, 이로 인해 디버깅 시간이 길어졌다.
최종 풀이 코드
import java.io.*;
import java.util.*;
class Room {
int e;
long v;
public Room(int e, long v) {
this.e = e;
this.v = v;
}
}
class Main {
static final int MAX_N = 5000;
static int n;
static ArrayList<Room>[] list;
static long[] memo;
public static void main(String[] args) throws IOException {
init();
bfs();
long ans = 0;
for (int i = 1; i < n; i++) {
ans = Math.max(ans, memo[i]);
}
System.out.println(ans);
}
public static void bfs() {
Deque<Room> dq = new ArrayDeque<>();
dq.addLast(new Room(0, 0));
while (!dq.isEmpty()) {
Room r = dq.poll();
int e = r.e;
long v = r.v;
for (Room room : list[e]) {
if (memo[room.e] == 0) {
memo[room.e] = v + room.v;
dq.addLast(new Room(room.e, memo[room.e]));
}
}
}
}
static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
memo = new long[n];
list = new ArrayList[n];
for (int i = 0; i < n; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken());
list[a].add(new Room(b, c));
list[b].add(new Room(a, c));
}
}
}
Java
복사
시간 복잡도
•
O(N)
◦
각 노드는 한 번씩만 방문되며, 간선의 수는 N-1이므로 전체 시간 복잡도는 O(N)
오늘의 회고
어려웠던 점
•
가중치 C의 범위가 최대 10억이라는 점을 간과해서 처음에는 int로 구현했고, 이로 인해 시간도 오래 걸리고 디버깅도 오래 했다.
•
문제 자체는 BFS 구조를 잘 이해하고 있다면 쉽게 풀 수 있는 문제였지만, 데이터 범위 조건을 꼼꼼히 확인하지 않은 점이 발목을 잡았다.
개선점
•
문제를 처음 접할 때, 입력값의 범위와 자료형 조건을 반드시 확인하는 습관을 들이자.
•
트리 구조 문제를 접할 때는 BFS/DFS 기반 누적합 접근법을 적극 활용할 수 있도록 연습하자.