[Jungol] 정올 3008 교통수단 선택하기

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2281&sca=50&page=20

 Input 

4 6 99 2

1 2 3

1 3 4

1 4 7

2 3 3

2 4 5

3 4 2

2 3

30 10 3

200 1000

 

 Output 

3600 

해당 문제는 BFS로 해결하는 문제로 중복 방문 확인을 visited[도시][남은 시간][교통수단] 3차원 배열을 이용합니다.

ex) visited[x][y][z] = x 도시에 y초를 남기고 z 교통수단으로 방문 비용

      → 동일한 조건으로 더 좋은 비용이 아닌한 중복 방문 허용 X

 

- 차로 도착하는 경우에는 도착지에 렌트카 지점이 있어야 합니다.

  즉, 도착지에 렌트카 지점이 있으면 렌트카 타고 왔어도 반납할 수 있으므로 도착 처리

  if) 도착지점에 방문해서도 렌트카 지점이 없다면 차를 반납하지 못하므로 도착했다고 볼 수 없으며

      이 경우 다른 가까운 지점에 차를 반납하고 자전거나 열차로 도착함에도 결과적으로 가장 효율적일 수 있습니다.

      왜냐하면 교통수단에 따라 비용이나 거리가 제각각이기 때문입니다.

 

- 선택한 교통수단에 따라 거리 대비 소요시간, 비용 처리 주의

 Input 

3 3 100 2

1 2 10

2 3 1

1 3 4

1 2

30 5 1

2 1000

 

 Output 

10 

---

- 인접리스트로 그래프 구현

- 단순 Queue로 구현

#include <stdio.h>
enum {
    BICYCLE = 0,
    CAR = 1,
    TRAIN = 2,
};
inline int min(int A, int B) { return A < B ? A : B; }
const int MAX_N = 100;
const int MAX_TIME = 1000;
const int INF = 2e9;
// 도시, 간선, 남은시간, 렌트카 지점 수
int N, M, T, L;
struct Node {
    int ID, dist;
    Node* next;
    Node* alloc(int _ID, int _dist, Node* _next) {
        ID = _ID, dist = _dist, next = _next;
        return this;
    }
}buf[MAX_N * MAX_N], * head[MAX_N + 5];
int bcnt;
 
struct Person {
    int pos, time, cost, use;
}que[MAX_N * MAX_N * MAX_N];
int fr, re;
int ans = INF;
int visited[MAX_N + 5][MAX_TIME + 5][3], rent[MAX_N + 5];
int trafficCost[3], trafficTime[3];
void connectEdge(int s, int e, int dist) {
    head[s] = buf[bcnt++].alloc(e, dist, head[s]);
}
 
void push(Person cur, Node* next, int traffic) {
    // 선택한 교통수단에 따른 거리 대비 남은 시간 계산
    int nextTime = cur.time - (next->dist * trafficTime[traffic]);
    // 남은 시간 초과
    if (nextTime < 0) return;
    // 선택한 교통수단에 따른 비용 계산
    int nextCost = cur.cost + (next->dist * trafficCost[traffic]);
 
    // 동일한 조건으로 방문시 비용적으로 좋지 않은 경우 제외
    if (visited[next->ID][nextTime][traffic] <= nextCost) return;
 
    // 이미 최종적으로 구한 비용보다 좋지 않은 경우
    if (nextCost > ans) return;
    // 방문 표시 후, Queue push
    visited[next->ID][nextTime][traffic] = nextCost;
    que[re++] = { next->ID, nextTime, nextCost, traffic };
}
void BFS() {
    // visited[][][] 초기화
    for (int i = 0; i < MAX_N + 5; ++i) {
        for (int j = 0; j < MAX_TIME + 5; ++j) {
            for (int k = 0; k < 3; ++k) {
                visited[i][j][k] = INF;
            }
        }
    }
    // 3가지 교통수단으로 출발
    for (int i = 0; i < 3; ++i) {
        if (i == CAR) {
            // 출발지에 지점이 있는 경우
            if (rent[i]) {
                // 도시, 남은시간, 누적비용, 교통수단
                que[re++] = { 1, T, 0, i };
                visited[1][T][CAR] = 0;
            }
        }
        else {
            // 자전거 혹은 열차
            que[re++] = { 1, T, 0, i };
            visited[1][T][i] = 0;
        }
    }
 
    while (fr < re) {
        Person cur = que[fr++];
        // 시간 초과한 경우
        if (cur.time < 0) continue;
        if (cur.pos == N) {
            // 차를 타고 왔지만 반납가능한 도착지인 경우
            if (cur.use == CAR && rent[N]) {
                ans = min(ans, cur.cost);
                continue;
            }
            // 자전거나 열차로 도착하는 경우
            // 차를 타고 온 경우, 렌트카 지점이 없는 경우 계속 BFS 탐색
            if (cur.use != CAR) {
                ans = min(ans, cur.cost);
                continue;
            }
        }
        for (Node* p = head[cur.pos]; p; p = p->next) {
            // 현재 지점에서 이동할 수 있는 교통 수단 선택
            for (int i = 0; i < 3; ++i) {
                // 현재 지점에서 렌트카를 선택하는 경우
                if (i == CAR) {
                    // 기존에 렌트카를 타고 있거나, 렌트 지점인 경우
                    if (cur.use == CAR || rent[cur.pos]) {
                        push(cur, p, i);
                    }
                }
                else { // 자전거나 기차를 선택
                    // 렌트카를 타고 있는 경우 반납하지 않고는 다른 교통 수단 불가
                    if (cur.use == CAR) {
                        // 렌트카를 반납하고 자전거나 열차를 선택
                        if (rent[cur.pos]) push(cur, p, i);
                    }
                    else { // 기존에 자전거나 열차를 연속적으로 선택
                        push(cur, p, i);
                    }
                }
            }
        }
    }
}
 
void input() {
    // 도시, 간선, 남은시간, 렌트카 지점 수
    scanf("%d %d %d %d", &N, &M, &T, &L);
    // 도시간 연결 거리
    int s, e, dist;
    for (int i = 0; i < M; ++i) {
        scanf("%d %d %d", &s, &e, &dist);
        connectEdge(s, e, dist);
        connectEdge(e, s, dist);
    }
    // 렌트카 지점
    int rentCity;
    for (int i = 0; i < L; ++i) {
        scanf("%d", &rentCity);
        rent[rentCity] = 1;
    }
    // 자전거, 렌트카, 기차의 거리당 시간
    for (int i = 0; i <= 2; ++i) {
        scanf("%d", &trafficTime[i]);
    }
    // 렌트카, 기차의 거리당 비용
    for (int i = 1; i <= 2; ++i) {
        scanf("%d", &trafficCost[i]);
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    BFS();
    printf("%d", ans);
}

- 인접 행렬로 그래프 표현

- 우선순위 큐 구현

- 사실상 자전거와 열차는 렌트카 지점같은 개념이 없기 때문에 비용 처리에서만 다르게 처리.

#include <stdio.h>
 
const int INF = 2e9;
int N, M, T, L;
int dist[101][101]; // 도시간 거리
int rent[101]; // 렌트카 지점 유무(1:존재,  0:없음)
int time[4]; // 거리당 시간
int cost[4]; // 거리당 비용
// [도시][시간][0]: 자전거나 고속열차, [1]:렌트카
int visit[101][1001][2];
struct Heap {
    int n, t, m, c;
}heap[100 * 1000 * 2];
int maxn;
void input() {
    int i, s, e, d;
    scanf("%d %d %d %d", &N, &M, &T, &L);
    
    for (i = 0; i < M; i++) {
        scanf("%d %d %d", &s, &e, &d);
        dist[s][e] = dist[e][s] = d; //양방향
    }
    for (i = 0; i < L; i++) {
        scanf("%d", &s);
        rent[s] = 1;
    }
    for (i = 1; i <= 3; i++) {
        scanf("%d", &time[i]);
    }
    scanf("%d %d", &cost[2], &cost[3]);
}
int comp(int a, int b) {
    if ((heap[a].c < heap[b].c) ||
        ((heap[a].c == heap[b].c) && (heap[a].t >= heap[b].t))) return 1;
    return 0;
}
 
void push(int n, int t, int m, int c) {
    if (t < 0) return; //남은 시간 없음
    if (visit[n][t][m] <= c) return; //이전보다 안좋음
    visit[n][t][m] = c;
    heap[++maxn].n = n; heap[maxn].t = t; heap[maxn].m = m; heap[maxn].c = c;
    int C = maxn, P = C / 2;
    while ((P > 0) && (comp(P, C) == 0)) {
        Heap temp = heap[P]; heap[P] = heap[C]; heap[C] = temp;
        C = P; P = C / 2;
    }
}
Heap pop() {
    Heap ret = heap[1]; heap[1] = heap[maxn--];
    int P = 1, L = 2, R = 3, C;
    while (L <= maxn) {
        if (R > maxn) C = L;
        else C = (comp(L, R) == 1) ? L : R;
        if (comp(P, C) == 1) break;
        Heap temp = heap[P]; heap[P] = heap[C]; heap[C] = temp;
        P = C; L = P * 2; R = L + 1;
    }
    return ret;
}
int BFS() {
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= T; j++) {
            visit[i][j][0] = visit[i][j][1] = INF;
        }
    }
    maxn = 0;
    push(1, T, 0, 0);
    while (maxn > 0) {
        Heap d = pop();
        if (visit[d.n][d.t][d.m] < d.c) continue;//의미 없는 확산이므로 스킵
        if (d.n == N) {
            if ((d.m == 1) && (rent[N] == 1)) return d.c;
            if (d.m == 0) return d.c;//도착,     성공
        }
        for (int i = 1; i <= N; i++) {
            int k = dist[d.n][i];
            if (k == 0) continue;
            if ((d.m == 1) || (rent[d.n] == 1)) { // 렌트카 타고 왔거나 지점 있음
                push(i, d.t - k * time[2], 1, d.c + k * cost[2]);
                if (rent[d.n] == 0) continue; // 다른 교통 수단 이용 불가
            }
            push(i, d.t - k * time[1], 0, d.c);// 자전거
            push(i, d.t - k * time[3], 0, d.c + k * cost[3]);// 고속열차
        }
    }
    return -1;
}
 
int main() {
    input();
    printf("%d\n", BFS());
    return 0;
}