ehsk2315   11달 전

DFS 로 풀어보려고 정수로도 빼보고 다 해봤는데도 도저히 답이 안나오네요 

DFS 더 좋은 풀이로 인해 해결할 수 있는지 궁금합니다..

결국 BFS 로 제출했지만..

hero00   11달 전

아슬아슬하게 돌긴 하네요

ehsk2315   11달 전

와.. 한수 배웠습니다... JVM 까지 내려가서 해야됐었네요

// S1 효율적인 해킹 DFS 최적화 메모리 관리
// 와 금방 풀었는데 이게 시간초과를 해결하는 과정이 너무 험난했다
// 처음에는 가장 긴 경로르르 구하는 건줄알았는데 알고보니 연결된 노드의 개수였다 즉
// 섬의 개수이다.
// 시간 초과 원인 1
// for 문에서 매번 visit 배열을 재 생성하는거 10000번의 객체 생성과 가비지 컬렉션의 비용이 누적
// Arrays.fill 로 해결

// 시간 초과 원인 2
// 정적 변수로 선언된 정적 배열에 직접 접근
// 재귀 호출 마다 Heap 메모리에 참조 연산 발생
// cnt 라는 지역변수에 누적해서 반환하고 이를 반복문에서 1번만 저장
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer>[] adj;
    static int[] res;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        adj = new ArrayList[N + 1];
        res = new int[N + 1];
        visit = new boolean[N + 1];

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

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            adj[B].add(A);
        }

        int max = 0;

        for (int i = 1; i <= N; i++) {
            Arrays.fill(visit, false);
            res[i] = dfs(i);
            max = Math.max(max, res[i]);
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            if (max == res[i]) {
                sb.append(i).append(" ");
            }
        }
        System.out.println(sb);
    }

    static int dfs(int idx) {
        visit[idx] = true;

        int cnt = 1;
        for (int next : adj[idx]) {
            if (!visit[next]) {
                cnt += dfs(next);
            }
        }
        return cnt;
    }
}

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