글 읽기 - [Java] 시간초과 에러

kimho314 3년 전 0

Java 이용해서 아래와 같이 짰는데 시간초과 에러가 뜹니다.

전혀 이유를 못 찾아서 도움주실분 구합니다 ㅠㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Queue;

public class Main
{
    private static int N;
    private static int M;
    private static int startNode;
    private static int endNode;

    private static List<Map<Integer, Integer>> adj = new ArrayList<>(N+1);

    private static int start = 1000000000;
    private static int end = 1;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs1 = br.readLine().split(" ");
        N = Integer.parseInt(inputs1[0]);
        M = Integer.parseInt(inputs1[1]);

        for(int i=0; i<N+1; i++)
        {
            Map<Integer, Integer> map = new HashMap<>();
            adj.add(map);
        }

        for(int i=0; i<M; i++)
        {
            String[] inputs2 = br.readLine().split(" ");
            int x = Integer.parseInt(inputs2[0]);
            int y = Integer.parseInt(inputs2[1]);
            int weight = Integer.parseInt(inputs2[2]);
            
            Map<Integer, Integer> map1 = new HashMap<>();
            map1.put(y, weight);
            adj.add(x, map1);
            Map<Integer, Integer> map2 = new HashMap<>();
            map2.put(x, weight);
            adj.add(y, map2);
            
            start = Math.min(start, weight);
            end = Math.max(end, weight);
        }
        
        String[] inputs3 = br.readLine().split(" ");
        startNode = Integer.parseInt(inputs3[0]);
        endNode = Integer.parseInt(inputs3[1]);
        
        int result = start;
        while(start <= end)
        {
            int mid = (start + end) / 2;
            if(bfs(mid))
            {
                result = mid;
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
        
        System.out.println(result);
    }

    private static boolean bfs(int c)
    {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        Boolean[] visited = new Boolean[N+1];
        Arrays.fill(visited, false);
        visited[startNode] = true;

        while(!queue.isEmpty())
        {
            int x = queue.poll();
            Map<Integer, Integer> map = adj.get(x);
            map.forEach((y,weight)->{
                if(!visited[y] && weight >= c)
                {
                    visited[y] = true;
                    queue.add(y);
                }
            });
        }
        return visited[endNode];
    }
}

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

문제

문제

출처

ICPC

[Java] 시간초과 에러

kimho314 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말