글 읽기 - [Java] BFS 풀이방식 시간초과나는 이유가 있을까요?

sth4881 1년 전 0

질문 게시판에 논리적으로 설명된 답변이 없는것 같은데,

해결하신 고수분들께서는 어떻게 푸셨는직 궁금합니다.

package com.algorithm.baekjoon;

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

public class BOJ1325 {
    static int N, M, max;
    static boolean[] visited;
    static List<List<Integer>> list;
    static int bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.offer(start);
        int cnt = 1;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int i=0; i<list.get(cur).size(); i++) {
                int next = list.get(cur).get(i);
                if(!visited[next]) {
                    max = Math.max(max, ++cnt);
                    visited[next] = true;
                    q.offer(next);
                }
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            StringTokenizer token = new StringTokenizer(br.readLine());
            N = Integer.parseInt(token.nextToken());
            M = Integer.parseInt(token.nextToken());
            visited = new boolean[N+1];

            list = new ArrayList<>();
            for(int i=0; i<=N; i++) {
                list.add(new ArrayList<>());
            }

            for(int i=0; i<M; i++) {
                token = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(token.nextToken());
                int b = Integer.parseInt(token.nextToken());
                list.get(b).add(a);
            }

            Map<Integer, Integer> map = new HashMap<>();
            for(int i=1; i<=N; i++) {
                Arrays.fill(visited, false);
                map.put(i, bfs(i));
            }

            for(int i=1; i<=N; i++)
                if(map.get(i)==max) bw.write(i+" ");
            bw.close();
        } catch (IOException e) {
            e.getStackTrace();
        }
    }
}

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

문제

문제

출처

ICPC

[Java] BFS 풀이방식 시간초과나는 이유가 있을까요?

sth4881 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말