[Python] 백준 31649번 Milk Exchange

문제

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

입력

• The first line contains N and M.
• The second line contains a string s1s2…sNs_1s_2\ldots s_Ns1​s2​…sN​ consisting solely of the characters ‘L’ or ‘R’, denoting the direction each cow will pass their milk in.
• The third line contains integers a1,a2,…,aNa_1, a_2, \ldots, a_Na1​,a2​,…,aN​, the capacities of each bucket.

출력

• Output an integer, the sum of milk among all cows after M minutes.
• Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

입력 예제

3 1
RRL
1 1 1

5 20
LLLLL
3 3 2 3 3

출력 예제

2

14

문제 해석

• N마리의 소가 원형으로 줄을 지어있다
• 각 소들은 우유통을 가지고 있는데 처음에 이 우유통은 가득 차 있다.
• 매 분마다 소들은 문자열 'L', 'R'에 따라 우유를 교환한다.
  • -> L : 왼쪽, R : 오른쪽
• 모든 교환은 동시에 이루어지며 우유는 1리터씩 이동한다. 이동 후 소의 우유가 수용가능한 양을 초과하게 되면 초과된 우유는 잃게된다.
• 이렇게 했을 때 주어진 시간 후 남아있게 되는 우유의 양을 구하여라

문제 풀이

• 소 ->  노드, 방향 -> 간선이라고 생각하여 그래프를 만든 후 풀이
• 각 소마다 몇 번 우유를 받는지 계산한다. -> 각 노드별 진입차수를 계산
• 진입차수가 0인 노드를 찾아 딕셔너리에 넣은 후 이동을 시작한다.
• dict에 넣은 노드를 빼서 연산을 시작한다.
  • 이 때, 진입차수가 2이상이라면 우유의 양은 -1, +1이 되므로 그 전까지 우유를 이동시키며 계산한다.
• 이동을 마쳤다면 모은 우유의 양을 출발 노드에 value값으로 저장한다.
• 획득한 우유에서 손실한 우유를 빼면 m분후 남아있는 우유의 양을 알 수 있다.
  • 각 소의 buckt_capacity만큼 우유를 누적했으므로, 손실된 우유의 양은 경과된 m분이다.
  • 이 때 각 정점에서 획득한 우유가 m보다 크다면 우유는 m만큼만 손실되고, 그렇지 않다면 모든 우유가 손실된다.

코드

n,m = map(int,input().split())
direction = input()
bucket_capacities = list(map(int,input().split()))

in_degree = [0] * n
total_milk = sum(bucket_capacities)
move_idx = 0

# 각 소마다 몇 번 우유를 받는지 체크
for idx, dir in enumerate(direction):
    # 왼쪽으로 전달하는 경우
    if dir == 'L':
        if idx == 0:
            move_idx = n - 1
        else:
            move_idx = idx - 1
    # 오른쪽으로 전달하는 경우
    elif dir == 'R':
        if idx == n - 1:
            move_idx = 0
        else:
            move_idx = idx + 1

    in_degree[move_idx] += 1

# 진입차수가 0인 노드 찾기
start_cows = {}
for i in range(n):
    if in_degree[i] == 0:
        start_cows[i] = 0

# 0인 노드에서 출발해서 우유 누적시키기
for key in start_cows.keys():
    cow = key
    milk = 0
    # 진입차수가 2라면 이동 끝
    while in_degree[cow] < 2:
        milk += bucket_capacities[cow]
        # 왼쪽으로 전달하는 경우
        if direction[cow] == 'L':
            if cow == 0:
                cow = n - 1
            else:
                cow -= 1
        # 오른쪽으로 전달하는 경우
        elif direction[cow] == 'R':
            if cow == n - 1:
                cow = 0
            else:
                cow += 1
    start_cows[key] = milk

# 손실된 우유 계산
lost_milk = 0
for milk in start_cows.values():
    if milk >= m:
        lost_milk += m
    else:
        lost_milk += milk

print(total_milk - lost_milk)