111. 미래 도시

• 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다.

• 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.

• 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다.

  • 연결된 2개의 회사는 양방향으로 이동할 수 있다.

  • 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다.

• 방문 판매원 A는 소개팅에도 참여하고자 한다.

  • 소개팅 상대는 K번 회사에 존재한다.

  • 방문 판매원 A는 X 번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 차자가서 함께 커피를 마실 예정이다.

    • 즉 A는 1번 회사에서 출발해서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다.

• 방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오.

  • 이때 소개팅 상대와 커피를 마시는 시간 등은 고려하지 않는다.

N = 5, X = 4, K = 5이고 회사 간 도로가 7 개면서 각 도로가 다음과 같이 연결되어 있다.

(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), (3번, 5번), (4번, 5번)

이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1 - 3 - 5 - 4)로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있다.

• 입력조건

  • 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1 ≤ N, M ≤ 100)

  • 둘째 줄부터 M + 1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.

  • M + 2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1 ≤ K ≤ 100)

• 출력조건

  • 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.

  • 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

1. 플로이드 워셜을 이용한 풀이

INF = int(1e9)

n, m  = map(int, input().split())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

#자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
for a in range(n + 1):
  for b in range(n + 1):
    if a == b:
      graph[a][b] = 0

#각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
  #A와 B가 서로에게 가는 비용은 1이라고 설정
  a, b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1

#거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
x, k = map(int, input().split())

for k in range(n + 1):
  for a in range(n + 1):
    for b in range(n + 1):
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

#수행된 결과를 출력
#출발지: 1, 도착지: x
distance = graph[1][k] + graph[k][x]

#도달할 수 없는 경우
if distance >= INF:
  print("-1")
else:
  print(distance)

• 현재 문제에서 N의 범위가 100이하로 매우 한정적이므로 프로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있기 때문에, 구현이 간단한 플로이드 워셜 알고리즘을 이용하는 것이 유리하다.

• 1번 노드에서 X를 거쳐 K로 가는 최단거리 (1번 노드에서 X까지의 최단거리 + X에서 K까지의 최단 거리)라는 점이다.

C++ 코드

#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M)
int n, m;
// 2차원 배열(그래프 표현)를 만들기
int graph[101][101];

int main(void) {
    cin >> n >> m;

    // 최단 거리 테이블을 모두 무한으로 초기화
    for (int i = 0; i < 101; i++) {
        fill(graph[i], graph[i] + 101, INF);
    }

    // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            if (a == b) graph[a][b] = 0;
        }
    }

    // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
    for (int i = 0; i < m; i++) {
        // A와 B가 서로에게 가는 비용은 1이라고 설정
        int a, b;
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    // 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
    int x, k;
    cin >> x >> k;

    // 점화식에 따라 플로이드 워셜 알고리즘을 수행
    for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
            }
        }
    }

    // 수행된 결과를 출력
    int distance = graph[1][k] + graph[k][x];

    // 도달할 수 없는 경우, -1을 출력
    if (distance >= INF) {
        cout << "-1" << '\n';
    }
    // 도달할 수 있다면, 최단 거리를 출력
    else {
        cout << distance << '\n';
    }
}

Java 코드

import java.util.*;

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M), 거쳐 갈 노드(X), 최종 목적지 노드(K)
    public static int n, m, x, k;
    // 2차원 배열(그래프 표현)를 만들기
    public static int[][] graph = new int[101][101];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 101; i++) {
            Arrays.fill(graph[i], INF);
        }

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if (a == b) graph[a][b] = 0;
            }
        }

        // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
        for (int i = 0; i < m; i++) {
            // A와 B가 서로에게 가는 비용은 1이라고 설정
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        x = sc.nextInt();
        k = sc.nextInt();

        // 점화식에 따라 플로이드 워셜 알고리즘을 수행
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }

        // 수행된 결과를 출력
        int distance = graph[1][k] + graph[k][x];

        // 도달할 수 없는 경우, -1을 출력
        if (distance >= INF) {
            System.out.println(-1);
        }
        // 도달할 수 있다면, 최단 거리를 출력
        else {
            System.out.println(distance);
        }
    }
}