글 읽기 - 혹시 해당 코드 시간초과 뜨는 이유 알 수 있을까요..?

imonlyone 1년 전 0

최대한 줄여봤는데도 시간초과가 나와서 그렇습니다.

sort를 통해서 값을 정리하는 방식 말고 첫번 째 탐색 시 두 값을 비교해서 큰 값으로 탐색을 진행,

그 후 다음 탐색은 첫번 째 탐색 보다 큰 값으로 탐색을 진행하는것이 맞나요?

package PS;

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

public class Boj24479 {
    static int N, M, Start;
    static boolean[] visit;
    static ArrayList<Integer>[] arr;
    static ArrayList<Integer> answer = new ArrayList<>();
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        dfs(Start);
        check();
        System.out.println(sb);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Start = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            arr[idx].add(value);
            arr[value].add(idx);
        }
    }

    static void dfs(int i) {
        visit[i] = true;
        answer.add(i);

        // 오름차순 방문
        for (int y : arr[i]) {
            if (visit[y]) continue;

            dfs(y);
        }

        Collections.sort(answer);
    }

    static void check() {
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                answer.add(0);
            }
        }

        for (int i = 0; i < answer.size(); i++) {
            sb.append(answer.get(i)).append('\n');

        }
    }
}

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

문제

문제

출처

ICPC

혹시 해당 코드 시간초과 뜨는 이유 알 수 있을까요..?

imonlyone 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말