글 읽기 - JAVA-11 1753 : 최단경로 다익스트라 시간초과 질문

97psh 1년 전 0

최단 경로 구하는 문제입니다. 먼저 플로이드로 접근했으나 시간초과 걸려서 다익스트라로 변경하였고, 인접행렬 사용시 메모리 초과가 발생하여 Map을 사용하였습니다.

메모리 초과를 해결하니 다시 시간초과가 뜨네요.

Map이 연결리스트랑 속도차이가 그렇게 많이 날까요.?

아니면 무엇 때문에 시간초과가 나는 걸까요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Pair implements Comparable<Pair> {
    int a;
    int b;

    public Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Pair o) {
        return this.a - o.a;
    }

    @Override
    public String toString() {
        return this.a + " " + this.b;
    }
}

public class Main {

    static class FastIn {
        BufferedReader br = null;
        StringTokenizer st = null;

        public FastIn() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            if (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

    // 연결리스트 기반
    public static void dijkstra(int start) {
        PriorityQueue<Pair> pQ = new PriorityQueue<>();
        pQ.add(new Pair(0, start));

        distance[start] = 0;

        while (!pQ.isEmpty()) {
            Pair cP = pQ.poll();
            int dist = cP.a;
            int now = cP.b;

            if (edges[now] == null) {
                edges[now] = new HashMap<Integer, Integer>();
            }
            if (distance[now] < dist)
                continue;
            for (int i = 1; i < distance.length; i++) {
                if (!edges[now].containsKey(i))
                    continue;
                int cost = dist + edges[now].get(i);
                if (distance[i] > cost) {
                    distance[i] = cost;
                    edges[start].put(i, cost);
                    pQ.add(new Pair(cost, i));
                }
            }
        }

    }

    static Map<Integer, Integer>[] edges;
    static double[] distance;

    public static void main(String[] args) {
        FastIn st = new FastIn();

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = st.nextInt();
        int eNum = st.nextInt();
        int start = st.nextInt();

        distance = new double[n + 1];
        edges = new HashMap[n + 1];
        final double MAX = Double.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            distance[i] = MAX;
        }

        // 배열 초기화
        for (int i = 1; i <= eNum; i++) {
            int v, e, w;
            v = st.nextInt();
            e = st.nextInt();
            w = st.nextInt();
            if (edges[v] == null)
                edges[v] = new HashMap<Integer, Integer>();
            edges[v].put(e, w);
        }
        // 다익스트라
        dijkstra(start);

        for (int i = 1; i <= n; i++) {
            try {
                if (start == i)
                    bw.write(0+"\n");
                else if (edges[start] == null || !edges[start].containsKey(i))
                    bw.write("INF\n");
                else
                    bw.write(edges[start].get(i)+"\n");
                bw.flush();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        try {
            bw.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

djm03178 1년 전 2

인접 행렬 대신 인접 리스트를 쓰셨다고 했지만 결국 구현한 코드는 인접 행렬이나 마찬가지입니다. 없는 원소를 리스트에 넣지 않았을 뿐이지, 다익스트라를 하는 과정에서 결국 모든 정점에 대해 간선이 존재하는지 여부를 확인하고 있기 때문입니다. 그렇게 할 필요 없이, 리스트 안에 있는 원소들만 탐색하면 됩니다.

97psh 1년 전 0

와 감사합니다.

정말로 Map 내부에 있는 것만 탐색해도 정상적으로 수행되네요.

하지만 틀렸습니다가 뜨는 걸 보니 코드를 다시 봐야겠네요 ㅋㅋ.

97psh 1년 전 0

질문 게시판 탐색 결과 틀렸습니다가 뜨는 이유는 동일한 정점에 여러개에 간선이 존재할 수 있다는 조건이 Map 사용으로 인해 무시되기 때문이었습니다.

자료구조를 Map에서 연결리스트로 변경하였습니다.

변경 과정에서 iterator를 사용하여 탐색을 진행하는데 탐색중인 리스트에 원소를 추가하는 경우가 생겨 ConcurrentModificationException 오류가 발생하였습니다.

iterator를 listiterator로 변경하고 listiterator에 원소를 추가함으로 문제를 해결 할 수 있었습니다.

답변해주신 분 덕분에 해결 할 수 있었습니다. 감사합니다 ㅠㅠ.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Pair implements Comparable<Pair> {
    int a;
    int b;

    public Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Pair o) {
        return this.a - o.a;
    }

    @Override
    public String toString() {
        return this.a + " " + this.b;
    }
}

public class Main {

    static class FastIn {
        BufferedReader br = null;
        StringTokenizer st = null;

        public FastIn() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            if (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

    // 연결리스트 기반
    public static void dijkstra(int start) {
        PriorityQueue<Pair> pQ = new PriorityQueue<>();
        pQ.add(new Pair(0, start));

        distance[start] = 0;

        while (!pQ.isEmpty()) {
            Pair cP = pQ.poll();
            int dist = cP.a;
            int now = cP.b;

            if (distance[now] < dist || edges[now] == null)
                continue;
            for (ListIterator<int[]> iterator = edges[now].listIterator(); iterator.hasNext();) {
                int[] list = iterator.next();
                int key = list[0];
                int val = list[1];
                int cost = dist + val;
                if (distance[key] > cost) {
                    distance[key] = cost;
                    if (start == now)
                        iterator.add(new int[] {key, cost});
                    else edges[start].add(new int[] {key, cost});
                    pQ.add(new Pair(cost, key));
                }
            }
        }

    }

    static LinkedList<int[]>[] edges;
    static double[] distance;

    public static void main(String[] args) {
        FastIn st = new FastIn();

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = st.nextInt();
        int eNum = st.nextInt();
        int start = st.nextInt();

        distance = new double[n + 1];
        edges = new LinkedList[n + 1];
        final double MAX = Double.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            distance[i] = MAX;
        }

        // 배열 초기화
        for (int i = 1; i <= eNum; i++) {
            int v, e, w;
            v = st.nextInt();
            e = st.nextInt();
            w = st.nextInt();
            if (edges[v] == null)
                edges[v] = new LinkedList<>();
            edges[v].add(new int[] {e, w});
        }
        // 다익스트라
        dijkstra(start);

        for (int i = 1; i <= n; i++) {
            try {
                if (start == i)
                    bw.write(0+"\n");
                else if (distance[i] == MAX)
                    bw.write("INF\n");
                else
                    bw.write((int)distance[i]+"\n");
                bw.flush();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        try {
            bw.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

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

문제

문제

출처

ICPC

JAVA-11 1753 : 최단경로 다익스트라 시간초과 질문

97psh 1년 전 0

djm03178 1년 전 2

97psh 1년 전 0

97psh 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말