Shiny Sky Blue Star

프로그래머스 문제 풀이/프로그래머스 (JAVA)

JAVA 백준 1753 최단경로 (그래프, 다익스트라)

gamja00 2025. 4. 15. 16:00

https://www.acmicpc.net/problem/1753

문제

  1. 첫째 줄에 정점의 개수 V (1 <= V <= 20000)와 간선의 개수 E (1 <= E <= 300000)가 주어진다.
  2. 둘째 줄에는 시작 정점의 번호 K (1 <= K <= V)가 주어진다.
  3. 셋째 줄부터 E개의 줄에 각 간선을 나타내는 세 개의 정수  u, v, w (u != v, 0 <= w <=10) 가 순서대로 주어진다. (정점 u에서 정점 v로 가는 가중치 w인 간선)
  4. V개의 줄에 걸쳐 i번째 줄에 i번 정점으로 가는 최단 경로의 경로값을 출력한다. 이 때 시작점과 동일한 정점일 때는 0을 출력하고, 시작점에서 i번 정점에 도달할 수 없을 경우 INF를 출력한다.

 

원래 가중치를 사용하는 그래프는 dfs를 사용해서 만들기 때문에 이 문제도 그렇게 풀려고 해봤는데 실행 시간이 조금 길 것 같기도 하고 조금 문제가 있을 것 같아 찾아보니 bfs를 이용하여 만드는 사람들이 많은 것 같아 bfs로 만들어보기로 했다.

 

 

 

초기 코드

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

public class Main {
    public static class Node {
        int data;
        int weight;

        public Node(int data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    }

    public static ArrayList<Node>[] list;
    public static boolean[] visited;
    public static int[] result;

    public static void bfs(int start) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Node num = queue.poll();
            for (int i = 0; i < list[num.data].size(); i++) {
                if (!visited[list[num.data].get(i).data]) {
                    result[list[num.data].get(i).data] = Math.min(num.weight + list[num.data].get(i).weight, result[list[num.data].get(i).data]);
                    queue.offer(new Node(list[num.data].get(i).data, result[list[num.data].get(i).data]));
                }
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(br.readLine());

        list = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        result = new int[V + 1];

        for (int i = 1; i < V + 1; i++) {
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            list[Integer.parseInt(st.nextToken())].add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        bfs(K);

        for (int i = 1; i < V + 1; i++) {
            if (i == K){
                System.out.println(0);
            } else if (result[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            }else {
                System.out.println(result[i]);
            }
        }
    }
}

 

2퍼센트에서 메모리 초과가 난 코드이다.

아마 정점이 최대 개수일 때 모두를 방문하게 된다면 너무 많은 메모리를 소비하게 되는 것 같다.

 

가중치를 이용하여 가중치가 작은 것부터 먼저 큐에 들어가면 많이 줄 것 같아서 이렇게 만들어봐야겠다.

 

이 때 가중치를 작은 것부터 넣어야 될 때 처음에 만들어진 그래프 배열을 정렬할지, 큐에 들어간 노드들을 정렬하기 위해 우선 순위 큐를 쓸지 정해야 된다.

 

별로 어려울 건 없으니 둘 다 해보겠다.

 

 

먼저 만들어진 그래프를 정렬하여 그대로 큐에 넣는 방법.

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

public class Main {
    public static class Node {
        int data;
        int weight;

        public Node(int data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        public int getWeight() {
            return this.weight;
        }
    }

    public static ArrayList<Node>[] list;
    public static boolean[] visited;
    public static int[] result;

    public static void bfs(int start) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Node num = queue.poll();
            for (int i = 0; i < list[num.data].size(); i++) {
                if (!visited[list[num.data].get(i).data]) {
                    result[list[num.data].get(i).data] = Math.min(num.weight + list[num.data].get(i).weight, result[list[num.data].get(i).data]);
                    queue.offer(new Node(list[num.data].get(i).data, result[list[num.data].get(i).data]));
                }
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(br.readLine());

        list = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        result = new int[V + 1];

        for (int i = 1; i < V + 1; i++) {
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            list[Integer.parseInt(st.nextToken())].add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        for (int i = 1; i < V + 1; i++) {
            list[i].sort(Comparator.comparing(Node::getWeight));
        }

        bfs(K);

        for (int i = 1; i < V + 1; i++) {
            if (i == K) {
                System.out.println(0);
            } else if (result[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(result[i]);
            }
        }
    }
}

 

똑같이 메모리 초과가 발생했다.

별로 좋은 방법이 아닌 것 같다.

아마 새로운 수들이 큐에 들어갔을 때 새로운 노드가 가중치가 더 작아도 그대로 들어가기 때문인 것 같다.

 

우선순위 큐를 이용하도록 하자.

 

 

우선순위 큐를 이용한 코드

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

public class Main {
    public static class Node {
        int data;
        int weight;

        public Node(int data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    }

    public static ArrayList<Node>[] list;
    public static boolean[] visited;
    public static int[] result;

    public static void bfs(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt((Node o) -> o.weight));
        queue.offer(new Node(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Node num = queue.poll();
            for (int i = 0; i < list[num.data].size(); i++) {
                if (!visited[list[num.data].get(i).data]) {
                    result[list[num.data].get(i).data] = Math.min(num.weight + list[num.data].get(i).weight, result[list[num.data].get(i).data]);
                    queue.offer(new Node(list[num.data].get(i).data, result[list[num.data].get(i).data]));
                }
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(br.readLine());

        list = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        result = new int[V + 1];

        for (int i = 1; i < V + 1; i++) {
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            list[Integer.parseInt(st.nextToken())].add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        bfs(K);

        for (int i = 1; i < V + 1; i++) {
            if (i == K) {
                System.out.println(0);
            } else if (result[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(result[i]);
            }
        }
    }
}

 

어 왜 메모리 초과지

-> dfs 썼다고 생각하고 큐에서 꺼낸 정점 위치의 방문 배열의 상태를 변경하는 걸 까먹었다.

 

 

최종 코드

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

public class Main {
    public static class Node {
        int data;
        int weight;

        public Node(int data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    }

    public static ArrayList<Node>[] list;
    public static boolean[] visited;
    public static int[] result;

    public static void dijkstra(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt((Node o) -> o.weight));
        result[start] = 0;
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node num = queue.poll();

            if (!visited[num.data]) {
                visited[num.data] = true;
                for (int i = 0; i < list[num.data].size(); i++) {
                    if (!visited[list[num.data].get(i).data]) {
                        result[list[num.data].get(i).data] = Math.min(num.weight + list[num.data].get(i).weight, result[list[num.data].get(i).data]);
                        queue.offer(new Node(list[num.data].get(i).data, result[list[num.data].get(i).data]));
                    }
                }
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(br.readLine());

        list = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        result = new int[V + 1];

        for (int i = 1; i < V + 1; i++) {
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            list[Integer.parseInt(st.nextToken())].add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        dijkstra(K);

        for (int i = 1; i < V + 1; i++) {
            if (result[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(result[i]);
            }
        }
    }
}

 

bfs로 썼던 함수 이름도 dijkstra로 변경하였다.

 

큐에서 꺼낸 정점을 방문하지 않았을 때 방문 리스트에서 정점 인덱스의 상태를 변경하고 우선순위 큐에 새로운 정점을 삽입할 수 있도록 한다.

 

새로운 정점을 우선순위 큐에 삽입할 때 기존의 간선보다 새롭게 추가된 간선의 크기가 작으면 새롭게 추가된 간선의 값으로 간선 값을 변경하도록 한다.

 

 

'프로그래머스 문제 풀이 > 프로그래머스 (JAVA)' 카테고리의 다른 글

JAVA 프로그래머스 Lv.3 연속 펄스 부분 수열의 합  (0) 2025.03.25
JAVA 프로그래머스 Lv.3 가장 먼 노드  (0) 2025.03.23
JAVA 프로그래머스 Lv.3 표현 가능한 이진트리  (0) 2025.03.19
JAVA 프로그래머스 Lv.3 110 옮기기  (0) 2025.03.12
JAVA 프로그래머스 Lv.3 불량 사용자  (2) 2024.12.28

'프로그래머스 문제 풀이/프로그래머스 (JAVA)'의 다른글

  • 현재글JAVA 백준 1753 최단경로 (그래프, 다익스트라)

관련글

티스토리툴바