[BOJ-28360] 양동이 게임

ParkJunHa·2023년 8월 4일

구현 그래프 이론 다이나믹 프로그래밍 시뮬레이션

BOJ

목록 보기

48/85

[Silver I] 양동이 게임 - 28360

문제 링크

성능 요약

메모리: 31256 KB, 시간: 40 ms

분류

다이나믹 프로그래밍, 그래프 이론, 구현, 시뮬레이션

문제 설명

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

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

풀이

아이디어

가장 먼저 생각난 것은 그냥 그래프 빡구현이였다. 단순하게 생각해서 유향그래프를 만든 뒤, 두가지 경우의 분기를 정해주었다.

해당 양동이에서 더이상 갈 수 있는 호스가 없는 경우
호스가 있어 아래로 흐를 수 있는 경우

1번의 경우 가장 밑바닥까지 내려간 경우이므로, result에 저장된 값과 비교해 더 큰것을 result로 넣는다.
2번의 경우는 연결된 호스의 개수 $n$ 으로 나눈 뒤, 재귀호출하여 그 아래 연결된 양동이로 이동한다. 가장 밑바닥까지 탐색하고 난 뒤에는 상위 양동이의 물을 0으로 만들어준다.

n, m = map(int, input().split())
graph = {i+1:[] for i in range(n)}
water = [0] * (n+1); water[1] = 100
result = 0

for i in range(m):
    k, v = map(int, input().split())
    graph[k].append(v)

def water_fall(bowl):
    global result, water
    if len(graph[bowl]) == 0:
        result = max(result, water[bowl])
        return
    
    for i in graph[bowl]:
        water[i] = water[bowl] / len(graph[bowl])
        water_fall(i)
    water[bowl] = 0

water_fall(1)
print(result)

위 코드의 경우에는 서로 다른 상위 노드에서 호스가 합쳐지는 아래의 경우를 처리하지 못한다.
문제에서 "연결하는 양동이가 같은 호스가 여러 개 주어지지 않는다." 라는 조건을 잘못 이해한 케이스

예를 들면 아래와 같은 경우이다.

이 경우에는 가장 밑바닥으로 물이 합쳐진다. 따라서 water_fall함수의 for문 안에서 처리해주는 water[i]를 업데이트 해주는것이 아니라 누적해줌으로서 이를 해결할 수 있다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = {i+1:[] for i in range(n)}
water = [0] * (n+1); water[1] = 100
result = 0

for i in range(m):
    k, v = map(int, input().split())
    graph[k].append(v)

def water_fall(bowl):
    global result, water
    if len(graph[bowl]) == 0:
        result = max(result, water[bowl])
        return
    
    for i in graph[bowl]:
        water[i] += water[bowl] / len(graph[bowl])
        water_fall(i)
    water[bowl] = 0


water_fall(1)
print(result)

하지만 재귀를 이용했더니 시간초과가 발생한다. 로직에는 문제가 없다고 판단하고 이를 그대로 바텀업으로 바꿔 풀었다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = {i+1:[] for i in range(n)}
water = [0] * (n+1); water[1] = 100
result = 0

for i in range(m):
    k, v = map(int, input().split())
    graph[k].append(v)

for i in range(1, n+1):
    for j in graph[i]:
        water[j] += water[i] / len(graph[i])

for i in range(1, n+1):
    if len(graph[i]) == 0:
        result = max(result, water[i])

print(result)