[27주차_금요일] 합승 택시 요금

[baexxbin]

• 사이트: 프로그래머스(PG)
• 문제: 합승 택시 요금
• 번호: 72413
• 레벨: Level3

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• $3 \leq n (지점 갯수: 노드 개수) \leq 200$
• $2 \leq fares 배열 크기 \leq n \times (n - 1) / 2 $
  • 양방향 간선이므로, 간선의 개수: $fares 배열 크기 \times2$
• 간선의 개수와 노드의 개수가 작기 때문에, BFS, DFS, Dijkstra 뭐든 풀이할 수 있을 것이라고 생각함

💡 풀이 아이디어

택시를 같이 탔다가 따로 가는 지점을 모든 노드에서 확인해준 뒤, 최소 비용 구하기

총 다익스트라를 $1 + N$ 번 진행

• 첫 번째 다익스트라
  • 시작 지점에서부터 모든 노드까지 최소 거리 구하기
• N번의 다익스트라
  • i 지점에서부터 따로 간다고 했을 때, i 지점에서부터 모든 노드까지 최소 거리 구하기

변수	설명
ArrayLIst<int[]>[] adj	int[][] fares를 양방향 그래프로 나타냈을 때, 인접리스트 정보

1. fares를 통해 인접리스트 만들기

   • ArrayList<int[]>[] adj(int n, int[][] fares)

2. 시작점으로부터 각 노드까지의 거리 구하기

   • int[] dis = dijkstra(adj, s): 시작점으로부터 각 노드까지의 거리 구하기

3. 따로 가는 지점을 각각 확인해주면서, 걸리는 비용 구하기

   • int[] tmp = dijkstra(adj, i): i 지점에서부터 각 노드까지의 거리 구하기
   • 이 때, 시작점에서 A, B가 집까지 갈 때 소요되는 비용
     • dis[i] + tmp[a] + tmp[b]
     • 따라서 정답을 구하기 위해서는 Math.min(dis[i] + tmp[a] + tmp[b], answer)를 해줘야 됨

• int[] dijkstra(ArrayList<int[]>[] adj, int s): 시작점 s로부터 각 노드까지 가는 거리를 구하는 함수

  static int[] dijkstra(ArrayList<int[]>[] adj, int s) {
  	int[] dis = new int[adj.length];
  	boolean[] v = new boolean[adj.length];
  	
  	Arrays.fill(dis, Integer.MAX_VALUE);
  	
  	dis[0] = 0;
  	PriorityQueue<Node> q = new PriorityQueue<Node>(Comparator.comparingInt(o -> o.c));
  	
  	q.add(new Node(s, 0));
  	dis[s] = 0;
  	
  	while(!q.isEmpty()) {
  		Node current = q.poll();
  		
  		if(v[current.e]) continue;
  		v[current.e] = true;
  
  		for(int[] next: adj[current.e]) {
  			
  			if(dis[current.e] + next[1] < dis[next[0]]) {
  				dis[next[0]] = dis[current.e] + next[1];
  				
  				q.add(new Node(next[0], dis[next[0]]));
  			}
  		}
  	}
  	return dis;
  }

N + 1번의 다익스트라를 해줘도 괜찮을거라고 생각했는데, 방문처리를 안해주면 7, 8번에서 시간초과가 나네요?,,,
왜 그런지 아시는 분 계신가요,,!

[jmxx219]

🤔 시간복잡도 고려사항

• 3 ≤ n ≤ 200
• 플로이드 와샬 시간 복잡도 -> O(n^3) -> O(200^3)

💡 풀이 아이디어

1. 플로이드 와샬 -> 모든 노드 간의 최소 요금 구하기

   for(int k = 1; k <= n; k++) {
   	for(int i = 1; i <= n; i++) {
   		if(edge[i][k] == INF) continue;
   		for(int j = 1; j <= n; j++) {
   			if(edge[k][j] == INF) continue;
   			if(edge[i][j] > edge[i][k] + edge[k][j]) {
   				edge[i][j] = edge[i][k] + edge[k][j];
   			}
   		}
   	}
   }

2. 구한 요금 바탕으로 합승 택시 최소 비용 구하기

   int answer = Math.min(INF, edge[s][a] + edge[s][b]);
   for(int i = 1; i <= n; i++) {
   	if(i == s) continue;
   	int cost = Math.min(INF, edge[s][i] + edge[i][a] + edge[i][b]);
   	answer = Math.min(answer, cost);
   }

   • 합승하는 구간(i)를 바탕으로 최소 비용 구하면서 결과값에 업데이트

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 200

=> 완전탐색 가능
=> 다익스트라, 플로이드도 가능

💡 풀이 아이디어

• 모든 정점에서의 최단 거리를 구해야 하므로 "플로이드 와샬" 사용
• 플로이드 와샬

      // 1. 플로이드 와샬 : 모든 정점까지의 최소거리 구하기
      for (int k = 1; k <= n; k++) {
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= n; j++) {
                  if (g[i][j] > g[i][k] + g[k][j]) {
                      g[i][j] = g[i][k] + g[k][j];
                  }
              }
          }
      }

• 합승해야 하므로, 중간 지점을 고려해서 다시 최솟값 구하기
  • s -> i에서 합승 + i -> a + i -> b

      // 2. 중간 지점을 거쳤을 경우도 포함
      for (int i = 1; i <= n; i++) {
          answer = Math.min(answer, g[i][s] + g[i][a] + g[i][b]);
      }

[baexxbin]

🤔 시간복잡도 고려사항

• 3 ≤ n ≤ 200
• 다익스트라 시간복잡도: O(ElogE)

💡 풀이 아이디어

• 각 지점을 시작 노드로 다익스트라 돌리기

  • 시작 지점: 출발지부터 i번째까지 합승하는 최소 비용 구하기
  • A,B 지점: A,B지점부터 i번째까지 합승하는 최소 비용 구하기 == i지점부터 각 A,B지점으로 가는 최소 비용

  private static int[] dijkstra(int n, int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
  
        PriorityQueue<Node> que = new PriorityQueue<>();
        que.offer(new Node(start, 0));
  
        while (!que.isEmpty()) {
            Node cur = que.poll();
  
            if (cur.cost > dist[cur.idx]) continue;
  
            for (Node nxt : adj.get(cur.idx)) {
                if (dist[nxt.idx] > dist[cur.idx] + nxt.cost) {
                    dist[nxt.idx] = dist[cur.idx] + nxt.cost;
  
                    que.offer(new Node(nxt.idx, dist[nxt.idx]));
                }
            }
        }
        return dist;
    }

• 각 다익스트라 내용을 바탕으로 최소 비용 구하기

  • ans = Math.min(ans, start[i]+startA[i]+startB[i]);
  • i지점까지 합승한 후, i지점부터 각 A,B로 갔을때 최소 비용

        int ans = INF;
        for (int i = 1; i < n + 1; i++) {   // 가능한 모든 합승지점i 찾기
            ans = Math.min(ans, start[i]+startA[i]+startB[i]);
        }
  
        return ans;

[jewan100]

🤔 시간복잡도 고려사항

• 3 ≤ n ≤ 200 → $2 \times 10^2$이므로 $O(N^4)$ 간당간당
• 모든 지점에 대해서 최단 거리를 계산 → 플로이드 와샬 $O(N^3)$

💡 풀이 아이디어

• 일단 모든 지점에 대해서 최단 거리를 계산 → 플로이드 와샬

  public void floydWarshall(int[][] graph, int n) {
      for (int k = 1; k <= n; k++) {
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= n; j++) {
                  if (graph[i][k] + graph[k][j] < graph[i][j]) {
                      graph[i][j] = graph[i][k] + graph[k][j];
                  }
              }
          }
      }
  }

• 합승을 하는 조건이 있으므로 중간 지점에 대해서 한번 더 최단 거리 계산을 해줘야 함

  floydWarshall(graph, n);
  for(int i = 1; i <= n; i++) {
      int total = graph[s][i] + graph[i][a] + graph[i][b];
      if (total < answer) {
          answer = total;
      }
  }

첨에 쫄았던 문제였는데 다시보니 쉽네요