합승 택시 요금

• A와 B가 목적지까지 도착하는 모든 경로를 계산 후 겹치는 구간을 빼는 방식으로 했을 때 최소 비용을 구하는 방식의 코드를 작성함.

• 코드가 너무 길어지고 모든 경로를 저장해놓아야 하며, 중간중간 방문했던 정점을 주기적으로 초기화 해주어야 하는 등의 여러 문제가 발생.

문제의 코드

import java.util.Vector;

class Node {
    private int vertex; // 노드 번호
    private Vector<Node> connectedNode = new Vector<Node>(); // 연결된 노드
    private Vector<Integer> weight = new Vector<Integer>(); // 연결된 노드의 가중치
    private boolean visited = false; // 방문 여부
    
    public Node(int vertext) {
        this.vertex = vertex;
    }
    
    public void setConnectedNode(Node node) {
        connectedNode.add(node);
    }
    public void setWeight(int w) {
        this.weight.add(w);
    }
    public void setVisited(boolean bool) {
        this.visited = bool;
    }
    public int getVertex() {
        return vertex;
    }
    public boolean getVisited() {
        return visited;
    }
    public Vector<Node> getConnectedNode() {
        return connectedNode;
    }
    public Vector<Integer> getWeight() {
        return weight;
    }
}

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        Vector<Node> nodeV = new Vector<Node>(); // 모든 노드의 정보를 담는 벡터
        Vector<Integer> numberOfCasesA = new Vector<Integer>();
        Vector<Integer> numberOfCasesB = new Vector<Integer>();
        
        for (int i = 1; i <= n; i++) {
            nodeV.add(new Node(i));
            // 벡터에 저장된 노드의 순서 == vertex - 1
        }
        // 벡터에 모든 노드 정보 추가
        for (int i = 0; i < fares.length; i++) { 
            Node node1 = nodeV.get(fares[i][0] - 1);
            Node node2 = nodeV.get(fares[i][1] - 1);
            int w = fares[i][2];
            node1.setConnectedNode(node2);
            node1.setWeight(w);
            node2.setConnectedNode(node1);
            node2.setWeight(w);
        }
        // A가 목적지까지 도착하는 모든 경우의 수
        Node startNode = nodeV.get(s - 1); // 출발지 노드
        startNode.setVisited(true); // 방문 표시
        for (int i = 0; i < startNode.getConnectedNode.size(); i++) { // 시작 정점에 연결된 간선의 수 만큼 반복
            if (startNode.getConnectedNode().getVertex() == a)
                
        }
        
        return answer;
    }
}

• 코딩 테스트 문제를 풀며 처음으로 벽에 부딪혔음.

• 알고리즘에 대한 숙지 없이 문제를 해결하려고 하다 보니 풀면 풀수록 점점 더 늪에 빠지는 듯한 느낌이었음.
• 처음에 찾았던 방법을 구현하는 과정에서 어려움을 느껴 다른 사람들이 올려준 구현 방법과, 2학년 2학기에 배운 Dijkstra을 교재를 보며 작성하였음.
• 사고 방식이 1차원적이라는 생각이 듦.
  → 문제를 다양한 방향에서 바라보는 관점을 가질 필요가 있음.
  → 문제 해결 후 다른 사람들은 어떻게 풀었나 해당 코드를 분석해 볼 것.
• 알고리즘에 대한 기본 지식이 부족함. 다양한 알고리즘을 문제를 풀어보며 익숙해 지는 과정이 필요함.

구현 방법

• 중간까지 합승해서 각자 찢어지기 에서 각자 위치에서 출발해서 합승지점에서 만나기로 문제를 다르게 생각할 수 있음.
• Dijkstra 알고리즘을 사용하여 s, a, b 3곳에서 출발하는 최소 비용 배열을 구해 각 3개 원소 합의 최소가 정답

소요 시간: 2시간 54분 10초

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        final int INF = 1000000; // 무한대, 연결이 없는 경우 
        int weight[][] = new int[n][n];
        
        int distanceFromStart[] = new int[n]; // 시작 정점에서 각 정점까지의 최단 거리
        int distanceFromA[] = new int[n]; // A의 도착 지점에서 각 정점까지의 최단 거리
        int distanceFromB[] = new int[n]; // B의 도착 지점에서 각 정점까지의 최단 거리
        boolean found[] = new boolean[n]; // 방문 여부
        
        // 모든 간선의 가중치 무한대로 저장
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < weight[i].length; j++) {
                if (i == j) {
                    weight[i][j] = 0;
                }
                else { 
                    weight[i][j] = INF;
                }
            }
        }
        
        // 모든 간선의 가중치 저장
        for (int i = 0; i < fares.length; i++) {
            for (int j = 0; j < fares[i].length; j++) { 
                weight[fares[i][0] - 1][fares[i][1] - 1] = fares[i][2];
                weight[fares[i][1] - 1][fares[i][0] - 1] = fares[i][2];
            }
        }
        shortestPath(distanceFromStart, found, n, weight, s - 1);
        shortestPath(distanceFromA, found, n, weight, a - 1);
        shortestPath(distanceFromB, found, n, weight, b - 1);
        
        answer = distanceFromStart[0] + distanceFromA[0] + distanceFromB[0];
        for (int i = 1; i < n; i++) {
            int distance = distanceFromStart[i] + distanceFromA[i] + distanceFromB[i];
            if (answer > distance) { 
                answer = distance;
            }
        }
        
        return answer;
    }
    public int choose(int distance[], int n, boolean found[]) { 
        int min = Integer.MAX_VALUE;
        int minpos = -1;
        for (int i = 0; i < n; i++) {
            if (distance[i] < min && !found[i]) {
                min = distance[i];
                minpos = i;
            }
        }
        return minpos;
    }
    public void shortestPath(int distance[], boolean found[], int n, int weight[][], int start) { 
        for (int i = 0; i < n; i++) { 
            distance[i] = weight[start][i];
            found[i] = false;
        }
        found[start] = true;
        distance[start] = 0;
        for (int i = 0; i  < n - 1; i++) {
            int u = choose(distance, n, found);
            found[u] = true;
            for (int w = 0; w < n; w++) { 
                if (!found[w]) {
                    if (distance[u] + weight[u][w] < distance[w]) {  
                        distance[w] = distance[u] + weight[u][w];
                    }
                }
            }
        }
    }
}

 public int choose(int distance[], int n, int found[]) { 
        int min = Integer.MAX.VALUE;
        int minpos = -1;
        for (int i = 0; i < n; i++) {
            if (distance[i] < min && !found[i]) {
                min = distance[i];
                minpos = i;
            }
        }
        return minpos;
    }

• 가중치가 가장 낮은 정점을 선택하는 이유는 Dijkstra 알고리즘의 핵심 원리가 탐욕적 선택(Greedy Selection) 이기 때문임.

• Dijkstra 알고리즘의 경우 "지금 당장 가까운 노드는 다른 곳을 거쳐서 가더라도 지금보다 더 짧아질 수 없다" 라는 가정을 바탕으로 함.

1. 시작점에서 직접 연결된 노드들 중 가장 가까운 노드를 u 라고 함.

2. 만약 u 보다 더 멀리 있는 v 노드를 거쳐서 u로 온다면 이미 v까지 가는 거리만으로도 u의 거리를 초과하게 됨.

→ 가장 짧은 거리를 가진 노드를 선택하는 순간, 그 노드까지의 거리는 확정됨.

// 핵심 코드
for (int w = 0; w < n; w++) { 
                if (!found[w]) {
                    if (distance[u] + weight[u][w] < distance[w]) {  
                        distance[w] = distance[u] + weight[u][w];    
                    }
                }
            }

weight = {{0, 7, INF, INF, 3, 10, INF},
		  {7, 0, 4, 10, 2, 6, INF},
          {INF, 4, 0, 2, INF, INF, INF},
          {INF, 10, 2, 0, 11, 9, 4},
          {3, 2, INF, 11, 0, INF, 5},
          {10, 6, INF, 9, INF, 0, INF},
          {INF, INF, INF, 4, 5, INF, 0}};

이고 u = 4, w = 1일 때,

• 시작 정점에서 u 정점까지의 가중치 = 3
• u 정점에서 1 정점까지의 가중치 = 2
• 시작 정점에서 1 정점까지의 가중치 = 7

→ 시작 정점에서 u 정점을 거쳐 가는게 더 빠름