글 읽기 - dfs 로 하면 런타임 오류 뜹니까??

hansorly 3년 전 0

계속 런타임 오류가 떠서 검색해보니 bfs를 두번 돌리는 형식으로 문제를 해결했더라고요

저는 1167번 문제처럼 dfs 로 2번 돌려서 해결하려고 했는데 100%에서 런타임 오류가 떠요

궁금해서 구글에 있는 다른분들의 블로그 자바 dfs 코드를 그대로 복붙해도 똑같이 런타임 오류가 떳어요 ..

c언어로 푼분들 dfs 코드를 봤는데도 제 코드와 다른점을 모르겠어요 ..

1167번도 dfs로 풀었는데 그건 재귀깊이가 최대 10만 까지 갈 수 있고 이 문제는 최대 1만 처럼 보이는데

무엇 때문에 런타임 오류가 뜬건지 도저히 모르겠습니다 .

index 떄문인것 같진 않은데 모르겠습니다 ..

import java.util.*;
import java.io.*;

public class Main {

    static int n;   
    static int dp[];
    static ArrayList<node> tree[];
    static boolean visit[];
    static int max= Integer.MIN_VALUE;
    static node mnode;

    
    public static void main(String[] args) throws IOException {
        // Scanner scanner = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
        n=Integer.parseInt(br.readLine());
        tree=new ArrayList[n+1];
        visit=new boolean[n+1];
    
        Arrays.fill(visit,false);

        for(int i=0;i<=n;i++){
            tree[i]=new ArrayList<node>();           
        }
     
        for(int i=1;i<n;i++){   
            String s[]= br.readLine().split(" ");
            int index = Integer.parseInt(s[0]);
            int idx = Integer.parseInt(s[1]);
            int dis=Integer.parseInt(s[2]);
            tree[index].add(new node(idx,dis));
            tree[idx].add(new node(index,dis));

        }
        dfs(tree[1].get(0),0);
        node temp=mnode;
        max=0;
        Arrays.fill(visit,false);
        mnode=null;
        dfs(temp,0);
        System.out.println(max);
    }
    static void dfs(node a,int val){
        int ret=0;
        int index=a.index;
        visit[index]=true;
      
        for(int i=0;i<tree[index].size();i++){
           
            int idx=tree[index].get(i).index;
            if(!visit[idx]){
                dfs(tree[index].get(i),val+tree[index].get(i).dis);
            }
        }
        if(val>max){
            max=val;
            mnode=a;
        }
    }
}
class node{
    int index;
    int dis;
   
        public node(int index,int dis){
            this.index=index;
            this.dis=dis;           
        }
}

jja08111 3년 전 2

https://www.acmicpc.net/board/view/50634

입력이 아래와 같은 경우를 고려해야 합니다.

//input
1
//answer
0

hansorly 3년 전 0

감사합니다 덕분에 고민 해결됐습니당 !!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs 로 하면 런타임 오류 뜹니까??

hansorly 3년 전 0

jja08111 3년 전 2

hansorly 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말