[BaekJoon][2593] 엘리베이터

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2005

2593 엘리베이터

https://www.acmicpc.net/problem/2593

1차 풀이 : DP

input을

elevator[층] : 각 층에서 갈 수 있는 엘리베이터 번호

fl[엘리베이터 번호] : 각 엘리베이터에서 갈 수 있는 층

들을 vector로 저장

dp[floor][elevator] : floor를 elevator로 도착할 때의 최소 이동    (floor 없어도 될 듯)

이동할 때 각 elevator를 중점으로 이동

요즘 DP 공부 중이라 DP 적으로 접근했는데 over한 듯...

답이 맞기는 하였지만 시간이 60ms가 나오기도 했고 이 풀이는 영 아닌것 같아서 다시 접근

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
#define INF    987654321
 
int n, m, A, B;
vector<int> floor_ele[100001], ele_floor[101];
int dp[100001][101], store[100001][101][2];
 
int go(int floor, int ele)
{
    int i, temp, mn, other, j;
 
    for (i = 0; i < ele_floor[ele].size(); i++) {
        other = ele_floor[ele][i];
        if (other == B)    return 0;
    }
    if (dp[floor][ele] != -1)    return dp[floor][ele];
    dp[floor][ele] = mn = INF;
 
    for (i = 0; i < ele_floor[ele].size(); i++) {
        other = ele_floor[ele][i];    // ele번 엘리베이터에 연결된 다른 층들
        if (other == floor)    continue;
        for (j = 0; j < floor_ele[other].size(); j++) {
            // 그 다른 층과 연결된 다른 엘리베이터
            if (floor_ele[other][j] == ele)    continue;
            temp = go(other, floor_ele[other][j]) + 1;
            if (temp < mn) {
                mn = temp;
                store[floor][ele][0] = other;
                store[floor][ele][1] = floor_ele[other][j];
            }
        }
    }
 
    return dp[floor][ele] = mn;
}
 
void solve()
{
    int i, temp, ans = INF, idx;
 
    memset(dp, -1, sizeof(dp));
    for (i = 0; i < floor_ele[A].size(); i++) {
        temp = go(A, floor_ele[A][i]) + 1;
        if (temp < ans) {
            ans = temp;
            store[A][0][0] = A;
            store[A][0][1] = floor_ele[A][i]; 
        }
    }
 
    if (ans >= INF)    ans = -1;
    printf("%d\n", ans);
    for (idx = 0, temp = A; ans > 0; ans--) {
        printf("%d\n", store[temp][idx][1]);
        i = store[temp][idx][0];
        idx = store[temp][idx][1];
        temp = i;
    }
}
 
int main()
{
    int i, x, y;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
 
        while (x <= n) {
            floor_ele[x].push_back(i);
            ele_floor[i].push_back(x);
            x += y;
        }
    }
    scanf("%d %d", &A, &B);
 
    solve();
 
    return 0;
}

2. BFS

이 문제의 핵심은 한번 탄 엘리베이터를 또 타지 않는다는 것이다. + 빨리 도착만 하면 되므로

층에 연결된 엘리베이터를 que에 넣어서 BFS

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
#define INF    987654321
 
int n, m, A, B;
vector<int> fl[101], elevator[100001];
queue<int> que;
int cnt[101], parent[101];
int last;
 
int bfs()
{
    int mn = INF;
 
    for (int i = 0; i < elevator[A].size(); i++) {
        int flag = 0;
        for (int j = 0; j < elevator[B].size(); j++) {
            if (elevator[A][i] == elevator[B][j])    flag = 1;
        }
        if (flag) {
            last = elevator[A][i];
            return mn = 1;
        }
        else {
            cnt[elevator[A][i]] = 1;
            que.push(elevator[A][i]);
        }
    }
 
    while (!que.empty()) {
        int ele = que.front();
        que.pop();
 
        for (int i = 0; i < fl[ele].size(); i++) {
            int other = fl[ele][i];
            if (other == B) {
                last = ele;
                return mn = cnt[ele];
            }
            else {
                for (int j = 0; j < elevator[other].size(); j++) {
                    if (cnt[elevator[other][j]] == 0) {    
                        cnt[elevator[other][j]] = cnt[ele] + 1;
                        parent[elevator[other][j]] = ele;
                        que.push(elevator[other][j]);
                    }
                }
            }
        }
    }
 
    return mn;
}
 
void print(int num)
{
    if (num == 0)    return;
    print(parent[num]);
    printf("%d\n", num);
}
 
int main()
{
    int x, y, ans;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
 
        while (x <= n) {
            fl[i].push_back(x);
            elevator[x].push_back(i);
            x += y;
        }
    }
    scanf("%d %d", &A, &B);
 
    ans = bfs();
    if (ans >= INF) {
        printf("-1\n");
    }
    else {
        printf("%d\n", ans);
        print(last);
    }
 
    return 0;
}

3. 다익스트라 (Dijkstra)

BFS로 문제를 풀고 보니 엘레베이터 간 연결을 graph로 표현하고 이를 최단경로 찾는 알고리즘을 이용하면 되겠다는 생각이 들어 다시 풀음

3_1 data 저장을 위와 같이 한 경우

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
#define INF    987654321
 
int n, m, start, goal;
vector<int> elevator[100001], flo[101];
int cnt[101], parent[101];
priority_queue<pair<int, int> > que;
 
void dijkstra()
{
    for (int i = 0; i < elevator[start].size(); i++) {
        cnt[elevator[start][i]] = 1;
        que.push(make_pair(-1, elevator[start][i]));
    }
 
    while (!que.empty()) {
        int ele = que.top().second;
        int c = que.top().first * -1;
        que.pop();
 
        if (c <= cnt[ele]) {
            for (int i = 0; i < flo[ele].size(); i++) {
                int other = flo[ele][i];
                for (int j = 0; j < elevator[other].size(); j++) {
                    int next = elevator[other][j];
 
                    if (cnt[next] == 0 || c + 1 < cnt[next]) {
                        cnt[next] = c + 1;
                        parent[next] = ele;
                        que.push(make_pair((c + 1) * -1, next));
                    }
                }
            }
        }
    }
}
 
void print(int num)
{
    if (num == 0)    return;
    print(parent[num]);
    printf("%d\n", num);
}
 
void solve()
{
    int ans = INF, last;
 
    dijkstra();
 
    // goal이랑 연결된 엘레베이터들 중에서 가장 최소 값 찾기
    for (int i = 0; i < elevator[goal].size(); i++) {
        if (cnt[elevator[goal][i]] < ans) {
            ans = cnt[elevator[goal][i]];
            last = elevator[goal][i];
        }
    }
 
    if (ans >= INF || ans == 0)    printf("-1\n");
    else {
        printf("%d\n", ans);
 
        // 그 최소값을 가진 엘레베이터의 parent들 찾아서 출력
        print(last);
    }
}
 
int main()
{
    int x, y;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        while (x <= n) {
            elevator[x].push_back(i);
            flo[i].push_back(x);
            x += y;
        }
    }
    scanf("%d %d", &start, &goal);
 
    solve();
 
    return 0;
}

3_2 data 저장을 엘리베이터간 연결만 graph로 표현한 경우

확실히 이 경우가 isLink 함수를 구현하는데 실수를 해서 골머리를 썩긴 했지만 메모리를 제일 적게 사용했다.

1등 소스 !~!

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
#define INF    987654321
 
int n, m, start, goal;
pair<int, int> input[101];
vector<int> elevator[101];
int cnt[101], parent[101];
priority_queue<pair<int, int> > que;
 
bool isLink(int first, int second)
{
    int buf = input[first].first - input[second].first;
    if (buf == 0)        return true;
    for (int i = 0; ; i++) {
        if (input[first].second * i + input[first].first > n)    break;
        int cal = input[first].second * i + buf;
        if (cal > 0 && cal % input[second].second == 0) {
            return true;
        }
    }
    return false;
}
 
void dijkstra()
{
    for (int i = 1; i <= m; i++) {
        int cal = start - input[i].first;
        if (cal >= 0 && cal % input[i].second == 0) {
            cnt[i] = 1;
            que.push(make_pair(-1, i));
        }
    }
 
    while (!que.empty()) {
        int ele = que.top().second;
        int c = que.top().first * -1;
        que.pop();
 
        if (c <= cnt[ele]) {
            for (int i = 0; i < elevator[ele].size(); i++) {
                int next = elevator[ele][i];
 
                if (cnt[next] == 0 || c + 1 < cnt[next]) {
                    cnt[next] = c + 1;
                    parent[next] = ele;
                    que.push(make_pair((c + 1) * -1, next));
                }
            }
        }
    }
}
 
void print(int num)
{
    if (num == 0)    return;
    print(parent[num]);
    printf("%d\n", num);
}
 
void solve()
{
    int ans = INF, last;
 
    dijkstra();
 
    for (int i = 1; i <= m; i++) {
        int cal = goal - input[i].first;
        if (cal >= 0 && cal % input[i].second == 0) {
            if (cnt[i] < ans) {
                ans = cnt[i];
                last = i;
            }
        }
    }
 
    if (ans >= INF || ans == 0)    printf("-1\n");
    else {
        printf("%d\n", ans);
        print(last);
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &input[i].first, &input[i].second);
        for (int j = 1; j < i; j++) {
            if (isLink(i, j)) {
                elevator[i].push_back(j);
                elevator[j].push_back(i);
            }
        }
    }
    scanf("%d %d", &start, &goal);
 
    solve();
 
    return 0;
}