[Algorithm] Exam - 물류창고

제품을 생산하는 N개의 공장 중 한 곳에 물류 창고를 지어서 제품을 관리할 예정이다.
제품을 신속하게 물류 창고로 옮겨야 하기 때문에 공장과 물류 창고 거리가 가까울수록 좋다.

물류 창고와 가장 먼 공장과의 거리가 최대한 가깝게 되는 장소에 물류 창고를 지으려고 한다.

 

[요구사항]

 

공장과 공장 사이에 최대 1개의 도로가 있을 수 있고, 양방향 도로이다.

제품의 이동은 도로를 이용해서만 이동이 가능하며 최단 거리로 이동을 한다.

최단 거리라 함은 A공장에서 B공장으로 이동할 때, A → B로 직접 가는 것보다 A → C → B로 가는 것이 더 짧은 거라면,

C공장을 거쳐서 이동하는 것이다.

 

값 범위

1. 공장 수 N(N = 자연수, 5 ≤ N ≤ 100)

2. 도로 정보 수 M(M = 자연수, 5 ≤ M ≤ N * (N -1) / 2)

3. A공장에서 B공장 거리 D(A, D = 자연수, 1 ≤ A,B ≤ N), (D = 자연수, 1 ≤ D ≤ 100)

 

예를 들어, N = 5, M = 7이고, 도로 정보가 아래 그림과 같은 경우 :

 

빨간색으로 표시된 부분이 각 장소에 물류 창고를 지었을 때, 물류 창고와의 거리가 제일 먼 공장이다.

행은 물류 창고 장소를 의미하고 열은 물류 창고와 해당 공장과의 거리를 의미한다.

 

1번 장소에 물류 창고를 지으면 5번 공장과의 거리가 18로 가장 멀고, 2번 장소에 지으면 5번 공장과의 거리가 20으로 가장 멀다.

5번 장소에 지으면 2번 공장과의 거리가 20으로 가장 멀다.

 

물류 창고를 3번이나 4번 공장에 지으면 제일 먼 공장과의 거리가 15로 다른 장소에 지었을 때보다 가깝게 된다.

 

공장 수 N과 도로 정보 수 M, 그리고 M개의 도로 정보가 주어졌을 때, 최적의 장소에 물류 창고를 지었을 때 가장 먼 공장과의 거리를 출력하시오.

 

[입력 형식]

첫 번째 줄에는 공장 수 N (N = 자연수, 5 ≤ N ≤ 100)과 도로 정보 수 M (M = 자연수, 5 ≤ M ≤ N * (N - 1) / 2) 이 공백으로 구분되어 입력

두 번째 줄부터 M 줄에 걸쳐 공장 A (A = 자연수, 1 ≤ A ≤ N)와 공장 B (B = 자연수, 1 ≤ B ≤ N) 와의 거리 D (D = 자연수, 1 ≤ D ≤ 100)가 공백으로 구분되어 입력 (양방향 도로이며 모든 공장은 연결됨을 보장함)

 

[출력 형식]

최적의 장소에 물류 창고를 지었을 때, 가장 먼 공장과의 거리를 출력

입/출력 예시

 

* 입출력 형식을 잘 지켜주세요.

 

#include <stdio.h>
int N, M;//공장 수, 도로 정보 수
int A[5000], B[5000], D[5000];//공장 A, 공장 B, 거리 D

void InputData(){
  int i;
  scanf("%d %d", &N, &M);
  for (i = 0; i < M; i++){
    scanf("%d %d %d", &A[i], &B[i], &D[i]);
  }
}

int main(){
  int ans = -1;
  InputData();//  입력 함수
  
  //  코드를 작성하세요
  
  printf("%d\n", ans);//  정답 출력
  return 0;
}

---

문제 접근 방법을 고려해보면 단순하게 <표>를 만들면 된다.

최대 100곳에 공장을 지었을 때, 다른 공장과의 거리를 구하면 된다.

각 장소에서 가장 먼 거리의 장소를 찾아, 그중에서 최소의 값을 찾으면 되겠다.

 

모든 노드 간의 최단 거리를 찾은 방법은?

- Floyd-Warshall Algorithm(Dynamic Programming)

- BFS

- Dijkstra

 

BFS와 Dijkstra는 비슷하다.

 

1. Floyd-Warshall Algorithm

- 동적 계획법(Dynamic Programming)으로 모든 노드 간의 최단거리를 구하는 알고리즘

 

for (k = 1; k <= N; k++) {    // 중간 경유 노드
    for (s = 1; s <= N; s++) {    // 출발 노드
    	for (e = 1; e <= N; e++) {    // 도착 노드
            if (dist[s][e] > dist[s][k] + dist[k][e]) {
                dist[s][e] = dist[s][k] + dist[k][e];
            }
        }
    }
}

 

출발 노드에서 목적지 노드까지의 거리보다 k를 거쳐갔을 때 더 좋으면, dist[s][e]를 변경한다.

Dynamic Programming은 점화식을 만들어야 한다.

A라는 장소에서 B라는 장소까지 도달하기 까지, 다양한 방법들이 존재하게 되는데, 그 길중에 최솟값을 고르는 것이다.

 

- 노드 간 거리가 링크 정보가 아닌 배열이어야 함 (dist[][]라는 2차원 배열 생성)

- 현재 갈 수 없는 곳은 큰 값으로 자기 노드는 0으로 초기화되어야 함

 

// 초기화 작업 실시
for (s = 1; s <= N; s++) {
    for (e = 1; e <= N; e++) {
        if (s != e) dist[s][e] = IMP;
        else dist[s][e] = 0;
    }
}

// 입력값 저장 실시
for (i = 0; i < M; i++) {
    dist[A[i]][B[i]] = dist[B[i]][A[i]] = D[i];
}

 

답을 찾는 방법은?

- 각 출발 노드에서 도착 노드까지 시간 중 최대 값을 구함

- 구한 최대 값 중에 최솟값을 찾으면 됨

 

ans = IMP;
for (s = 1; s <= N; s++) {    // 출발 노드
    max = 0;
    for (e = 1; e <= N; e++) {    // 도착 노드
        if (max < dist[s][e]) {
            max = dist[s][e];
        }
    }
    if (ans > max) ans = max;
}

---

BFS

- 출발 노드에서 다른 노드까지 최단 거리를 구할 수 있으므로 BFS를 N번 실행하면 됨

- BFS를 이용해서 최단 거리를 구한다 → 가중치가 다르다

 

1. 가중치가 동일한 경우 (중복 방문 불가)

- 1 → 2로 이동 시 거리가 1 임

- 1 → 3 → 2로 이동 시 거리가 2 임

- 나중에 방문하는 경우 비용이 같거나 더 안 좋음

- 중복 방문 불필요

 

 

 

2. 가중치가 다른 경우 (중복 방문 허용) - 일반 Queue를 이용하거나, 우선순위 Queue를 이용한다.

N이 작을 경우 두 가지 모두를 사용해도 큰 차이는 없으나, N이 큰 경우는 우선순위 Queue가 더 좋은 효율을 보인다.

- 1 → 2로 이동 시 거리가 3 임

- 1 → 3 → 2로 이동 시 거리가 2 임

- 나중에 방문하는 경우가 더 좋을 수 있음

- 중복 방문 필요

 

- 그럼, 무조건 중복 방문을 허용하면 될까?

안된다. 무조건 중복 방문을 허용하면 양방향 길의 원칙을 가지고 있기 때문에, 무한 반복을 시도할 경우가 생긴다.

중복 방문의 경우는 아래의 룰을 따른다.

 

- 중복 방문 판단 → 기존 값보다 좋을 경우만 중복 방문

- 그러기 위해서는 visit 배열을 큰 값으로 초기화해야 함

 

#define IMP (100 * 100 + 10)
int visit[110];

for (i = 1; i <= N; i++) {
    visit[i] = IMP;
}

// 갱신
/* visit 배열의 목적지 보다, 현재 방문한 visit 배열의 위치에서, cur에서 dst까지 가는 거리를 더한게
이전(visit 배열의 목적지)보다 좋을때만 확산(갱신)한다.*/

if (visit[dst] > visit[cur] + dist[cur][dst]) {
    visit[dst] = visit[cur] + dist[cur][dst];
}

 

큐

- visit 배열에 비용을 저장하므로, 큐에는 좌표(노드)만 저장하면 됨

- 중복 방문하므로 큐에 크기는 노드 개수보다 많아야 함(최소 10배, 안전하게 100배)

 

#define MAXQ (100 * 100)

int queue[MAXQ];
int wp, rp;

void push(int n, int t) {
    if (visit[n] <= t) return;
    visit[n] = t;
    queue[wp++] = n;    // 확산
}

int front() {
    return queue[rp];    // 읽기만 함
}

void pop() {
    rp++;    // 제거
}

int empty() {
    return wp == rp;
}

 

BFS 구현

- 초기화

- 시작 위치 큐에 저장

- 반복문

int BFS(int s) {    // 출발
    int i, tmp, max = 0;
    for (i = 1; i <= N; i++) {
        visit[i] = IMP;
    }
    
    wp = rp = 0;
    push(s, 0);
    
    /* 큐가 빌때까지 확산을 해주면 visit 배열에는 출발 노드부터 N번 노드까지 최단거리가 구해지게 된다.
    이 값들 중에서 최대값(가장 먼 공장)을 구해주면 된다. */
    while (!empty()) {
        tmp = front();
        pop();
        for (i = 1; i <= N; i++) {
            push(i, visit[tmp] + dist[tmp][i]);
        }
    }
    
    for (i = 1; i <= N; i++) {
        if (max < visit[i]) {
            max = visit[i];
        }
    }
    /* S -> 가장 먼 공장 거리 == max 
    이것을 N번 호출해주면 된다. */
    return max;
}

 

solve 구현

- 노드 간 거리 배열 초기화

- 링크 정보를 배열로 변환

- 각 노드마다 최단 거리로 가장 먼 값 중 최솟값 찾기

 

int solve() {
    int i, j, sol = IMP, ret;
    
    /* Floyd와 마찬가지로 노드간의 거리를 배열로 만드는 작업 필요 */
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= N; j++) {
            /* 자기 자신은 0이라고 해야하는데 왜 하지않았을까?
            왜냐하면 BFS에서는 자기 자신(출발 노드)는 가지 않기 때문에 필요가 없다. */
            dist[i][j] = IMP;
        }
    }
    
    for (i = 0; i < M; i++) {
        dist[A[i]][B[i]] = dist[B[i]][A[i]] = D[i];
    }
    /* -------------------------------------------- */
    for (i = 1; i <= N; i++) {
        /* (1번 ~ N번)에서 출발하여 가장 먼 거리를 Return(반복) 
        그 중 가장 짧은 거리의 공장 파악 */
        ret = BFS(i);
        if (sol > ret) sol = ret;
    }
    
    return sol;
}