BOJ 11952

23 Feb 2020 • ProblemSolving

좀비

문제출처

문제 해석

  • N개의 도시중, K개의 도시가 좀비에게 점령당했을 때 도시 1부터 N으로 이동하는데 드는 최단 비용을 구하는 문제입니다.
  • 좀비에게 점령당한 도시의 정보가 주어지고, 좀비도시로부터 S거리의 도시들은 위험한 도시라고 명명합니다.
  • 위험한 도시를 지날 때는 숙박비가 q원이 필요하고, 그 밖에 안전한 도시들은 p원이 필요합니다.
  • 좀비도시로는 이동할 수 없습니다.

설계(10)

  • 각 도시로 가는 비용을 갱신시키고, 다익스트라 알고리즘을 이용하여 최단 비용을 찾는 문제입니다.
  • 처음에 문제를 잘못이해한 부분은 도시로 가는데 드는 비용. 즉, 간선의 가중치를 갱신시키는 문제인 것으로 오해했습니다.
  • 알고보니 각 도시를 지나는 데 필요한 비용을 갱신하는 것이었습니다.
  • 좀비도시의 정보가 주어지기 때문에 각 좀비도시로 부터 S거리만큼 탐색하여 위험도시 여부를 가립니다.
  • 이후 다익스트라 알고리즘으로 최단거리를 갱신할 때, 마지막 도시가 아닌 도시중에서 위험한 도시면 q원, 안전도시면 p원을 추가하도록 하였습니다.(첫번째와 마지막 도시는 숙박비가 필요하지 않기 때문에 마지막 도시를 제외하도록 하였습니다)
  • 탐색을 진행할 때, 먼저 좀비도시인지 파악해서 탐색을 진행하지 않는 것도 중요한 부분이었습니다.

구현(40)

코드
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
#define MAXN 100001
#define INF 1e11
typedef long long ll;

vector<int> adj[MAXN];
ll dist[MAXN];
bool visited[MAXN];
int N,M,K,S;
ll p,q;
vector<int> zombi;
bool zombi_used[MAXN];
struct node{
    int cur;
    ll w;
    bool operator < (const node& a) const{
        return a.w < w;
    }
};
void bfs(){
    queue<pair<int,int> > q;
    for (int i = 0 ;i  < K; i++){
        q.push({zombi[i],0});
        visited[zombi[i]] = true;
    }
    while (!q.empty()){
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (cnt == S) continue;
        for (int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i];
            if (visited[next]) continue;
            visited[next] = true;
            q.push({next,cnt+1});
        }
    }
}
void dijkstra(){
    priority_queue<node> pq;
    pq.push({1,0});
    dist[1] = 0;
    while (!pq.empty()){
        int cur = pq.top().cur;
        ll cur_w = pq.top().w;
        pq.pop();
        if (dist[cur] != cur_w) continue;
        for (int i = 0 ;i < adj[cur].size(); i++){
            int next = adj[cur][i];
            ll next_w = cur_w;
            if (zombi_used[next]) continue;
            if (next != N) {
                if (visited[next]) next_w+=q;
                else next_w += p;
            }
            if (dist[next] > next_w){
                dist[next] = next_w;
                pq.push({next,dist[next]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K >> S;
    cin >> p >> q;
    for (int i = 1; i <=N; i++){
        dist[i] = INF;
    }
    for (int i = 0 ; i < K; i++){
        int tmp;
        cin >> tmp;
        zombi_used[tmp] = true;
        zombi.push_back(tmp);
    }
    for (int i = 0 ;i  < M; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    dijkstra();
    cout <<dist[N] <<"\n";
    return 0;
}
디버깅
  • 좀비도시로부터 위험도시여부를 탐색할 때 dfs를 이용해서 WA가 나왔습니다.
  • 잘 생각해보니 dfs를 이용하면 방문해야 할 곳을 방문하지 못하는 오류가 생깁니다.
  • 하나의 정점으로 모인 간선중에 하나는 방문을 끝내야 하고, 나머지 하나는 방문을 더 해야하는 상황일 때, 방문을 먼저 끝낸 간선으로 인해 다음 정점을 갈 수 없는 사례가 있습니다.
  • 이러한 오류를 방지할 수 있는 bfs탐색으로 변경하였습니다.
제출결과
  • 72ms

마무리

  • bfs+다익스트라를 이용한 문제였습니다. 각 알고리즘을 구현할 줄 알면 충분히 풀 수 있는 문제입니다.
 BOJ

Related Posts