백준 28283번 해킹[C++]

1. 문제 풀이

 안녕하세요. 오늘 풀어본 문제는 백준 28283번 해킹입니다. 알고리즘 유형은 그래프 탐색 이론 및 그리디 알고리즘입니다. 이 문제는 2023년 강원도 대학생 코딩 경진 대회 문제의 C번으로 출제된 문제입니다. 저는 이때, 찍먹으로 참여해 보았는데 당시에만 하더라도 C++ 문법도 모르고 알고리즘도 전혀 알지 못해 아무것도 하지 못했었는데요. 1년이 지난 지금 생각이 나서 다시 문제를 읽고 풀어보고 있습니다. 이번에 풀어보고 느낀 점은 대회장에선 디버깅 및 컴파일이 금지였습니다. 코드 작성은 메모장으로 진행했었습니다. 디버깅이 없으니 이 문제에서 막혀 아무것도 못했을 거 같긴 합니다. 서론은 여기까지 하고 문제 풀이 접근 방법은 다음과 같습니다.

 그래프는 양방향 비연결 그래프라고 생각했습니다. 이유는 정점의 개수에 비해 간선의 개수가 작으며 출력 시 돈을 무한히 얻을 수 있으면 -1을 출력하라고 한 것을 통해서 보안 프로그램이 설치되지 않는 정점이 존재한다는 의미입니다. 따라서 그래프는 비연결그래프입니다. 보안프로그램은 연결된 통신망을 통해 시간에 따라 확산되어 설치됩니다. 즉, 초기에 보안프로그램이 설치되는 컴퓨터와 거리가 멀수록 그 컴퓨터에서 얻을 수 있는 돈의 양을 미리 계산할 수 있습니다. 각 컴퓨터에 보안프로그램이 설치되는 시간은 너비 우선 탐색을 사용하여 구해주었습니다.

 그 다음, 각 컴퓨터에서 얻을 수 있는 비용과 보안프로그램이 설치되는 시간 정보를 활용해 각 컴퓨터에서 얻을 수 있는 비용을 새로 갱신해 줍니다. 이 과정에서 보안 프로그램이 설치되지 않았는데 얻을 수 있는 비용이 0이 아닌 컴퓨터가 있다면 -1을 출력하고 프로그램을 종료하였습니다.

 얻을 수 있는 비용이 갱신된 테이블을 내림차순으로 정렬한 다음, x개의 비용을 더하여 답을 출력하였습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m, x, y;
vi adj[500'005];
vpl cost;
ll security[500'005];
queue<int> q;

int main() {
  fastio(nullptr, false);

  cin >> n >> m >> x >> y;
  for(int i = 1; i <= n; i++){
    int c;
    cin >> c;
    cost.pb({c, i});
  }
  
  while(m--){
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
    adj[v].pb(u);
  }

  for(int i = 0; i < y; i++){
    int u;
    cin >> u;
    security[u] = 1;
    q.push(u);
  }

  while(q.size()){
    auto cur = q.front(); q.pop();
    for(auto nxt : adj[cur]){
      if(security[nxt] != 0 && security[nxt] <= security[cur] + 1) continue;
      security[nxt] = security[cur] + 1;
      q.push(nxt);
    }
  }

  for(auto &cur : cost){
    auto &[c, v] = cur;
    if(!security[v] && c){
      cout << -1;
      return 0;
    }
    c *= security[v]-1;
  }

  ll ans{};
  sort(rall(cost));
  for(int i = 0; i < x; i++){
    ans += cost[i].X;
  }
  cout << ans;
}

 

3. 제출 결과