KOI 2018 중등부 3번 / 물탱크 - 15972

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int N, M, H;
vector<vector<pair<int, int>>> adj;
vector<int> rest;
 
struct Node {
    int idx;
    int val;
};
 
bool operator<(const Node& n1, const Node& n2) {
    return n1.val < n2.val;
}
 
vector<Node> arr;
 
int convert(int u, int v) {
    return M*u+v;
}
 
void startpoint(int idx1, int idx2) {
    int c;
    for(int j = 0; j<idx2; ++j) {
        cin >> c;
        if(c == -1) continue;
        Node n;
        n.idx = convert(idx1, j);
        n.val = c;
        arr.push_back(n);
    }
}
 
void init() {
    cin >> N >> M >> H;
    arr = vector<Node>();
    rest = vector<int>(N*M+1, H);
    adj = vector<vector<pair<int, int>>>(N*M+1);
 
    int c;
    startpoint(0, M);
    for(int i = 0; i<N-1; ++i) {
        for(int j = 0; j<M; ++j) {
            cin >> c;
            if(c == -1) continue;
            adj[convert(i, j)].push_back(make_pair(convert(i+1, j), c));
            adj[convert(i+1, j)].push_back(make_pair(convert(i, j), c));
        }
    }
    startpoint(N-1, M);
 
    for(int i = 0; i<N; ++i) {
        cin >> c;
        if(c != -1) {
            Node n;
            n.idx = convert(i, 0);
            n.val = c;
            arr.push_back(n);
        }
        for(int j = 0; j<M-1; ++j) {
            cin >> c;
            if(c == -1) continue;
            adj[convert(i, j)].push_back(make_pair(convert(i, j+1), c));
            adj[convert(i, j+1)].push_back(make_pair(convert(i, j), c));
        }
        cin >> c;
        if(c != -1) {
            Node n;
            n.idx = convert(i, M-1);
            n.val = c;
            arr.push_back(n);
        }
    }
    for(int i = 0; i<arr.size(); ++i) 
        adj[N*M].push_back(make_pair(arr[i].idx, arr[i].val));
    
}
 
void bfs(int start) {
    priority_queue<Node> pq;
    Node n;
    n.idx = start;
    n.val = 0;
    pq.push(n);
 
    while(!pq.empty()) {
        int idx = pq.top().idx;
        int val = -pq.top().val;
        pq.pop();
        if(rest[idx] <= val) continue;
        rest[idx] = val;
 
        for(int i = 0; i<adj[idx].size(); ++i) {
            int there = adj[idx][i].first;
            int nval = max(val, adj[idx][i].second);
 
            if(rest[there] <= nval) continue;
            Node tmp;
            tmp.idx = there;
            tmp.val = -nval;
            pq.push(tmp);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    init();
    bfs(N*M);
    int sum = 0;
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<M; ++j) 
            sum += rest[convert(i, j)];
        
    cout << sum;
}

 

 

 

 

 

www.acmicpc.net/problem/15972

15972번: 물탱크

 

 

 

 

 

물탱크

우선 input을 적절히 처리해서 그래프의 형태로 데이터를 저장했습니다. 노드는 각각의 방이고, 간선은 방을 잇는 구멍으로 하였습니다.

문제를 해결하는 방법으로 가장 바깥으로 배수되는 구멍으로부터 거슬러 올라가면서 각각의 방에 물이 얼마만큼 남아있는지 계속 갱신해준다면, 정답을 구할 수 있습니다.

예를들어 3번방과 4번방이 k라는 높이의 구멍으로 연결되 있고 현재 3번방에서 4번방으로 이동하려면

1. 이제까지 통과해온 구멍중 가장 높이가 높은 구멍의 높이를 n이라는 변수에 저장한다. 즉 k가 n보다 크면 k를 n으로 갱신한다.

2. n보다 4번방에 물이 더 많은 경우, 4번방으로 이동하고, 4번방의 남은 물을 n로 갱신한다.

 

를 모든 바깥 배수로에 대해 다 따져 주면 됩니다.

처음엔 단순하게 dfs로 탐색했는데, 이미 탐색한 곳을 다시 방문할 수 있기 때문에 시간초과 났습니다.

따라서 bfs에 priority_queue를 사용하여 n의 값이 가장 작은 방부터 탐색을 하도록 하였습니다.

n은 n보다 더 큰 값을 만났을때 갱신됨으로 priority_queue에 새로 들어오는 원소의 n값은 빠져나간 원소의 값보다 더 작아질 수는 없고, 또한 한 방에 여러개의 구멍이 있더라도 n이 가장 작은 것부터 탐색되니 1번규칙에 의해 여러번 탐색 될 일이 없어집니다.