[문제 풀이] 프로그래머스 - 가장 먼 거리(java)

프로그래머스 - 가장 먼 거리(java)

---

https://school.programmers.co.kr/learn/courses/30/parts/14393

프로그래머스

 

프로그래머스 > 그래프 - 가장 먼 거리

문제를 풀면서 공부한 내용 입니다 !

 

1. 처음 제출한 코드 (플로이드-워샬 알고리즘)

2. 다음 제출한 코드 (다익스트라 알고리즘)

---

1. 처음 제출한 코드 (플로이드-워샬 알고리즘)

알고리즘 수업 시간에 그래프에 대해 배운 적이 있다.

개인적으로 그래프 문제 중에서 플로이드-워샬 알고리즘이 가장 간단하다고 생각해서

(공부할 때 가장 이해가 잘됐어서 허허..)

일단 제출해봤다.

 

// 메모리 & 시간 초과
class Solution {
    public int min(int a, int b) {
        if (a >= b) {
            return b;
        } else {
            return a;
        }
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        int[][] vertex = new int[n + 1][n + 1];
        
        // 그래프 초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                vertex[i][j] = 9999;
            }
        }
        
        // 그래프 생성
        for (int i = 0; i < edge.length; i++) {
            int start = edge[i][0];
            int end = edge[i][1];
            
            vertex[start][end] = 1;
            vertex[end][start] = 1;
        }
        
        // 최단 경로 업데이트 (플로이드-워셜 알고리즘 사용)
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    vertex[i][j] = min(vertex[i][j], vertex[i][k] + vertex[k][j]);
                }
            }
        }
        
        int max = 0;
        // 1번 노드에서 가장 먼 거리 구하기
        for (int i = 2; i <= n; i++) {
            if (max < vertex[1][i]) {
                max = vertex[1][i];
            }
        }
        
        // 가장 먼 거리를 가진 간선 노드의 개수 구하기
        for (int i = 2; i <= n; i++) {
            if (vertex[1][i] == max) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

테스트 6까지는 통과했지만, 플로이드-워샬 알고리즘은 시간 복잡도가 O(N^3)이기 때문에

테스트 7부터 메모리와 시간 초과가 발생했다.

 

- 플로이드-워샬 알고리즘

처음에 모든 거리를 모른다고 가정하여 9999로 초기화하고, 다음으로 간선이 존재하면 1로 초기화 했다.

[0][n], [n][0]은 사용하지 않을 것이기 때문에 모든 반목문은 1로 시작하도록 했다.

 

우리는 1->2로 갈 때는 최단 거리가 1임을 알고 있지만, 1->4로 갈 때는 거리를 알 수 없다.

그렇다면 어떻게 알 수 있는걸까?

 

바로 1->2, 2->4와 같이 연결되는 지점을 통하여 1->4로 이동할 수 있다는 사실을 활용하면 된다.

이 점을 이용하여 vertex[i][k] + vertex[k][j]와 같이 코드를 작성할 수 있고,

최단 경로를 업데이트 해야하기 때문에 vertex[i][j] = min(vertex[i][j], vertex[i][k] + vertex[k][j]); 가 된다.

 

그래서 최종적으로 위와 같이 코드를 작성할 수 있다.

 

2. 다음 제출한 코드 (다익스트라 알고리즘)

메모리와 시간을 신경 써서 코드를 작성하려면 더 효율적인 알고리즘이 필요했다.

다익스트라, 프림, 벨만-포드, 크루스칼, DFS, BFS 등.. 다양한 알고리즘이 존재한다.

 

각각 알고리즘마다 사용하는 목적이 있어서 코드를 작성하려고 했지만

개념이 가물가물해서 다시 찾아봤다.

 

이 문제는 주어진 정점에서 모든 다른 경로의 정점까지 최단 거리를 구하는 것이기에

다익스트라 알고리즘으로 구현해야하는 문제였다. 

 

앞으로 각 알고리즘의 특성과 개념을 확실하게 하고,

문제를 잘 읽고 풀어야겠다. (ㄱ-)

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        final int INF = 9999;
        
        // 그래프 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 생성
        for (int[] e : edge) {
            int start = e[0];
            int end = e[1];
            graph.get(start).add(new int[]{end, 1});
            graph.get(end).add(new int[]{start, 1});
        }

        // 다익스트라 알고리즘
        int[] distances = new int[n + 1];
        Arrays.fill(distances, INF);
        distances[1] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[]{1, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int distance = current[1];
            if (distance > distances[node]) continue;

            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                int nextDistance = distance + weight;
                if (nextDistance < distances[nextNode]) {
                    distances[nextNode] = nextDistance;
                    pq.offer(new int[]{nextNode, nextDistance});
                }
            }
        }

        // 최대 거리 찾기
        int maxDistance = 0;
        for (int i = 1; i <= n; i++) {
            if (distances[i] != INF && distances[i] > maxDistance) {
                maxDistance = distances[i];
            }
        }

        // 최대 거리를 가진 노드의 개수 세기
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (distances[i] == maxDistance) {
                answer++;
            }
        }

        return answer;
    }
}

 

- 다익스트라 알고리즘

다익스트라 알고리즘은 방문하지 않은 노드 중 가장 적은 비용을 가지는 노드를 선택하고

해당 노드로부터 갈 수 있는 노드들의 비용을 갱신하는 알고리즘이다.

이는 우선순위 큐와 순차 탐색으로 코드를 작성할 수 있다.

 

순차 탐색의 시간 복잡도는 O(N^2)이고, 위에서 O(N^3)일 때 오류가 생겼기 때문에

시간 복잡도가 O(E log V)인 우선순위 큐를 사용하고자 하였다.

 

1번 노드에서 6번 노드까지 최단 거리를 저장하는 distances 배열과

노드 방문 여부를 체크하는 pq 우선순위 큐를 사용해서 알고리즘을 작성했다.

 

int[] current = pq.poll(); 코드를 통해 우선순위 큐에서 정점과 거리를 current 배열에 저장한다.

for문을 통해 다음 노드까지의 최단거리를 갱신한다.

---

이번에는 다익스트라 문제를 풀어봤습니다.

다음 포스팅에서 만나봅시다요 !