글 읽기 - 이 문제는 DFS로 풀 수 없는건가요?

brad903 5년 전 0

안녕하세요! 어제 빼빼로 데이를 맞아 빼빼로가 들어간 문제를 찾다 풀었는데요.

시간초과 때문에 우여곡절이 있네요. 한 수 부탁드립니다. 아래는 제가 시도한 내용들입니다

일반적인 DFS로 문제 풀이

2. 시간초과의 발생으로 가지치기를 위해 현재 min이 answers 후보 중 가장 큰 값보다 작으면 그 즉시 탐색 종료하도록 변경(min이 더 커질일은 없기 때문에)

3. 그럼에도 불구하고 시간초과 발생으로 가중치가 큰 순서대로 먼저 탐색하도록 정렬(혹시나 큰수부터 하면 값이 큰 answers 후보를 빨리 찾을 수 있을까해서요).

그래도 아직 시간초과가 발생하네요.. ㅠ

package b13905;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    static List<List<Graph>> graph;
    static boolean[] check;
    static int endNum;
    static List<Integer> answers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] settingVal = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
        int vertexNum = settingVal[0];
        int edgeNum = settingVal[1];

        int[] startToEnd = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
        int startNum = startToEnd[0];
        endNum = startToEnd[1];

        graph = new ArrayList<>();
        check = new boolean[vertexNum + 1];
        for (int i = 0; i <= vertexNum; i++) {
            graph.add(new ArrayList<>());
            check[i] = false;
        }

        for (int i = 0; i < edgeNum; i++) {
            int[] vals = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
            graph.get(vals[0]).add(new Graph(vals[1], vals[2]));
            graph.get(vals[1]).add(new Graph(vals[0], vals[2]));
        }

        for (List<Graph> graphs : graph) {
            Collections.sort(graphs);  // 각 정점에서 가중치 큰 것 순서대로 정렬
        }

        dfs(startNum, 1000000);

        if(answers.isEmpty()) System.out.println(0);
        else System.out.println(Collections.max(answers));
    }

    static void dfs(int x, int min) {
        check[x] = true;
        for (int i = 0; i < graph.get(x).size(); i++) {
            if(!answers.isEmpty()) {  // answers에 더 큰수가 있으면 더이상 탐색말고 종료
                if(min <= Collections.max(answers)) return;
            }
            int tempEnd = graph.get(x).get(i).end;
            int tempWeight = graph.get(x).get(i).weight;
            int tempMin = Math.min(tempWeight, min);
            if(tempEnd == endNum) {
                answers.add(tempMin);
                return;
            }
            if(!check[tempEnd]) {
                dfs(tempEnd, tempMin);
                check[tempEnd] = false;
            }
        }
    }
}

class Graph implements Comparable {
    int weight;
    int end;

    public Graph(int end, int weight) {
        this.weight = weight;
        this.end = end;
    }

    @Override
    public int compareTo(Object o) {
        return ((Graph)o).weight - weight;
    }
}

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

문제

문제

출처

ICPC

이 문제는 DFS로 풀 수 없는건가요?

brad903 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말