💁♀️ DFS 사용!
핵심 아이디어
"임의의 노드에서 가장 긴 경로로 연결돼있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다."
우선 임의의 가장 긴 경로를 찾은 후, 해당 경로의 끝에서 반대로 다시 한 번더 탐색을 수행
결국 처음에 임의의 긴 경로를 찾는것은 정확한 출발노드를 정하기위함
임의의 노드에서 DFS(or BFS)수행시 각 노드의 거리(누적 합)를 배열에 저장해야함.
처음 탐색을 종료한 후 거리값이 최대인것의 노드에서 다시 한번더 탐색 수행해야함
Troubleshooting
class makeOne {
static List<graph>[] list;
static boolean[] visited, finished;
static int v;
static boolean cycle;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
v = Integer.parseInt(br.readLine());
list = new ArrayList[v+1];
visited = new boolean[v+1];
finished = new boolean[v+1];
for(int i=1; i<=v; i++) {
list[i] = new ArrayList<>();
finished[i] = false;
}
StringTokenizer st;
for(int i=0; i<v; i++) {
st = new StringTokenizer(br.readLine());
int here = Integer.parseInt(st.nextToken());
int next = Integer.parseInt(st.nextToken());
while(next != -1) {
list[here].add(new graph(next, Integer.parseInt(st.nextToken())));
next = Integer.parseInt(st.nextToken());
}
}
System.out.println(dfs(1));
}
public static long dfs(int start) {
visited[start] = true;
int max = 0;
int sum = 0;
for(graph g : list[start]) {
if(!visited[g.v]) {
sum += g.distance;
dfs(g.v);
}
}
finished[start] = true;
return Math.max(max, sum);
}
}
class graph {
int v;
int distance;
public graph(int v, int distance) {
this.v = v;
this.distance = distance;
}
}문제
예제 1의 결과가 2로 정답과 다르게 나왔다
원인
직접 손으로 돌려보니 2라는 결과는 내 코드상에서는 처음에 dfs(1)이 들어갔을 때 for문에서 g가 (3,2)로 빠지고 끝이었기에 그대로 2만 결과로 나온것이다.
그런데 조금 더 생각해보니, 이렇게짜서는 경로 구분이 안된다.
예를 들어, 예제 1상으로는 경로가 '1-2-3-4', '1-3-4-2'가 따로따로 검사되어야하는데, 내 코드로 돌아가면 1-3-4-5-2가 한번에 sum에 누적되며 검사된다. (중간에 종료되지않는 가정하에)
해결
핵심 아이디어를 참고했다.
"임의의 노드에서 가장 긴 경로로 연결돼있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다."
이 말이 처음에 이해가 안됐다.
내가 처음에 생각했을때는 단순히 저렇게만 생각하면 예외처리가안돼서 문제일거라고 생각했다.
즉 아래 이미지를 보면, 당장 1에서 출발할 때 2로 가는 길이가 4로가는 1보다 10으로 더 길지만, 결국 4로가서 3으로 가는게 최장거리이다.
이렇게 최장거리는 눈 앞의 경로로만 판단할 수 없다고 생각했다.
하지만 이 아이디어는 더 발전했다.
우선 임의의 가장 긴 경로를 찾은 후, 해당 경로의 끝에서 반대로 다시 한 번더 탐색을 수행하는것이다!
결국 처음에 임의의 긴 경로를 찾는것은 정확한 출발노드를 정하기위함이다.
Troubleshooting 2
import java.io.*;
import java.util.*;
class Main {
static List<graph>[] list;
static boolean[] visited, finished;
static int v;
static boolean cycle;
static long[] sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
v = Integer.parseInt(br.readLine());
list = new ArrayList[v+1];
visited = new boolean[v+1];
finished = new boolean[v+1];
sum = new long[v+1];
long max = 0;
int maxIndex = 0;
for(int i=0; i<=v; i++) {
list[i] = new ArrayList<>();
finished[i] = false;
}
StringTokenizer st;
for(int i=1; i<=v; i++) {
st = new StringTokenizer(br.readLine());
int here = Integer.parseInt(st.nextToken());
int next = Integer.parseInt(st.nextToken());
while(next != -1) {
list[here].add(new graph(next, Integer.parseInt(st.nextToken())));
next = Integer.parseInt(st.nextToken());
}
}
dfs(3); //trouble
for(int i=1; i<v+1; i++) {
if(max < sum[i]) {
max = sum[i];
maxIndex = i;
}
}
visited = new boolean[v+1];
sum = new long[v+1];
dfs(maxIndex);
long answer = 0;
for(int i=1; i<v+1; i++) {
if(answer < sum[i]) {
answer = sum[i];
}
}
System.out.println(answer);
}
public static void dfs(int start) {
visited[start] = true;
for(graph g : list[start]) {
if(!visited[g.v]) {
sum[g.v] = sum[start] + g.distance;
dfs(g.v);
}
}
}
}
class graph {
int v;
int distance;
public graph(int v, int distance) {
this.v = v;
this.distance = distance;
}
}
문제
예제1의 결과는 잘 나왔는데 제출해보니 '런타임 에러 (ArrayIndexOutOfBounds)'가 발생했다.
원인
처음에 임의의 노드를 3으로 잡아뒀다. v의 최소는 2이기때문에, 1혹은 2로잡아야한다.
아니면 경우에 맞게 넣어주기위해 random함수를 사용한다.
해결
dfs((int)Math.round(Math.random()+(v-1)));로 수정했다.
제출코드
import java.io.*;
import java.util.*;
class Main {
static List<graph>[] list;
static boolean[] visited, finished;
static int v;
static boolean cycle;
static long[] sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
v = Integer.parseInt(br.readLine());
list = new ArrayList[v+1];
visited = new boolean[v+1];
finished = new boolean[v+1];
sum = new long[v+1];
long max = 0;
int maxIndex = 0;
for(int i=1; i<=v; i++) {
list[i] = new ArrayList<>();
finished[i] = false;
}
StringTokenizer st;
for(int i=1; i<=v; i++) {
st = new StringTokenizer(br.readLine());
int here = Integer.parseInt(st.nextToken());
int next = Integer.parseInt(st.nextToken());
while(next != -1) {
list[here].add(new graph(next, Integer.parseInt(st.nextToken())));
next = Integer.parseInt(st.nextToken());
}
}
dfs((int)Math.round(Math.random()+(v-1)));
for(int i=1; i<v+1; i++) {
if(max < sum[i]) {
max = sum[i];
maxIndex = i;
}
}
visited = new boolean[v+1];
sum = new long[v+1];
dfs(maxIndex);
long answer = 0;
for(int i=1; i<v+1; i++) {
if(answer < sum[i]) {
answer = sum[i];
}
}
System.out.println(answer);
}
public static void dfs(int start) {
visited[start] = true;
for(graph g : list[start]) {
if(!visited[g.v]) {
sum[g.v] = sum[start] + g.distance;
dfs(g.v);
}
}
}
}
class graph {
int v;
int distance;
public graph(int v, int distance) {
this.v = v;
this.distance = distance;
}
}공부한 사항
- Math.random() = 0.0~1.0 사이 임의의값 반환
