글 읽기 - java/시간초과 .. 살려주세요 ㅠㅠ

sally3605 3년 전 0

dfs 의 depth 에 맞춰 알고리즘을 끝내도록 잘 짠 것 같은데 10%에서 쭉 시간초과가 뜹니다 ...

어떤 부분을 고쳐야할지 감이 아예 안오네요 .. 고수님들 도와주세요 ㅠㅠ 감사합니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    static int N, M;
    static boolean[][] friends;
    static boolean[] visit;
    static boolean isIt = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine(), " ");
        N = stoi(str.nextToken());
        M = stoi(str.nextToken());
        friends = new boolean[N][N];
        visit = new boolean[N];
//서로 친구인 경우 friends 배열에 저장해준다.
        for (int i = 0; i < M ; i++) {
            str = new StringTokenizer(br.readLine(), " ");
            int p1 = stoi(str.nextToken());
            int p2 = stoi(str.nextToken());
            friends[p1][p2] = true;
            friends[p2][p1] = true;
        }
//dfs() 실행으로 person 0 ~ N-1을 시작점으로 A~E 총 5명의 연결된 친구관계가 있는지 확인한다.
        for (int i = 0; i < N ; i++) {
            visit[i] = true;
            dfs(i, 1);
            visit[i] = false;
            if (isIt) //depth = 5인 경우가 나와ㅆ다면 다른 경우를 살펴볼 필요가 없으므로 break; 로 for문 종료
                break;
        }
//dfs 끝난게 depth = 5가 돼서 그런지 아닌지 판단. true 면 depth5 까지 간 것이 맞으므로 1 출력, 아니면 0
        if (isIt)
            System.out.println(1);
        else System.out.println(0);
    }
    public static void dfs(int person, int depth) {
        if (depth == 5) {
            isIt = true; //depth 5 진입하면 isIt을 true 처리하고 dfs return 으로 탈출
            return;
        }
        for (int j = 0; j < N ; j++) {
            if(!visit[j] && friends[person][j]) {
                visit[j] = true;
                dfs(j, depth+1);
                visit[j] = false;
            }
        }
    }
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
}

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

문제

문제

출처

ICPC

java/시간초과 .. 살려주세요 ㅠㅠ

sally3605 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말