[BOJ] 28360: 양동이 게임

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

BOJ - 양동이 게임

문제 유형 : 그리디, 그래프

문제 난이도 : Silver I

 

문제

찬우는 천하제일 코딩대회 참가자들과 간단한 게임을 하기로 했다. 게임은 '양동이 게임'으로, 맨 위의 양동이에 물을 100$만큼 부어 흘려보냈을 때 최종적으로 가장 많은 물이 담긴 양동이를 선택하면 이기는 게임이다. 양동이를 고르기 전까지는 연결 상태를 알 수 없다. 하지만 찬우는 양동이들이 어떻게 연결되어 있는지 이미 알고 있는 상태였다! 찬우가 게임을 이기기 위해서 골라야 하는 양동이에는 얼마만큼의 물이 들어있는지 알아보자.

 1번 양동이가 항상 맨 위에 있으며, 1의 양만큼 물이 채워져 있는 양동이에 K>0개의 나가는 방향 호스가 연결되어 있으면 양동이가 비워질 때까지 호스당 1/K 씩 흐른다. 또한 양동이의 번호가 더 작을수록 위에 있기 때문에, 물은 항상 번호가 작은 양동이에서 큰 양동이로 흐른다.

 

입력

첫째 줄에 양동이의 개수 N과 호스의 개수 M이 공백으로 구분되어 주어진다. (1≤N≤50; 0≤M≤100)

둘째 줄부터 M개의 줄에 걸쳐 호스의 정보를 나타내는 두 정수 v, w가 공백으로 구분되어 주어진다. (1≤v<w≤N) 이는 v번 양동이에서 w번 양동이로 물이 흐르는 호스가 있다는 뜻이다.

연결하는 양동이가 같은 호스가 여러 개 주어지지 않는다. 즉, 주어지는 모든(v, w)쌍은 서로 다르다.

 

출력

 1$번 양동이에 물을 100만큼 채워서 흘려보냈을 때, 한 양동이에 가장 많이 들어있는 물의 양을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10^{-6} 이하이면 정답으로 처리한다.

 

풀이

양동이를 정점, 호스를 간선이라 치고, 방향 그래프를 만든다.

무조건 작은 번호의 양동이가 큰 양동이로 주는 구조기에, bfs / dfs 말고, 단순 반복문으로 해결할 수 있다.

처음에 1번에 100.0의 물을 할당하고, 1번부터 순차적으로 다음 양동이들에게 (자신의 물양) / (진출차수)만큼 준다.

 

물양 배열의 최대값을 반환한다.

 

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main (int argc, char *argv[]) {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n+1);
  vector<float> water(n+1, 0.0);
  for(int i = 0; i < m; ++i) {
    int v, w;
    cin >> v >> w;
    graph[v].push_back(w);
  }

  water[1] = 100.0;

  for(int i = 1; i <= n; ++i) {
    int outdegree = graph[i].size();
    for(const auto &next : graph[i]) {
      water[next] += water[i] / outdegree;
    }
    if(outdegree > 0) water[i] = 0.0;
  }

  float maxWater = *max_element(water.begin(), water.end());
  cout << maxWater << "\n";
  return 0;
}