[Softeer] S1256 업무처리

[Softeer]

Question

Language: Python

말단 노드에서부터 업무를 처리해서 부서장까지 업무를 전달하면서 최종적으로 처리되는 업무량을 구하는 문제이다.

각 노드간에 간선을 통해 연결되어 있으며, 각각의 child node는 일을 처리하게 되면 parent node로 업무를 전달하게 된다.

Top-Down 방식으로 부서장에서 말단 직원 까지 순회하면서 업무를 처리하면 된다.

부서장이 하는 일

• 올라온 업무가 있으면 좌/우 자식 노드를 구분하여 업무 처리

if index==1:
    if task_map[index][1-(day % 2)]:
        completed_task_sum+=task_map[index][1-(day % 2)].popleft()

내부 직원이 하는 일

• 올라온 업무가 있으면 좌/우 자식 노드를 구분하여 업무 처리
• 처리한 직업에 대해서 부모 노드로 전송

if task_map[index][1-(day % 2)]:
    #처리한 작업을 올린다.
    task_map[index//2][index % 2].append(task_map[index][1-(day % 2)].popleft())

말단 직원이 하는 일

• 대기하고 있는 업무가 있으면 처리해서 부모노드로 전송

if tasks[index-2**h]:
    completed_task=tasks[index-2**h].popleft()
    task_map[index//2][index % 2].append(completed_task)

해당 작업을 R일 동안 반복하면 최종적으로 처리한 업무량을 구할 수 있다.

Solution

import sys
from collections import deque

def solution(day,index):
    global task_map,completed_task_sum

    #내부 직원인 경우
    if index < 2**h:
        
        #부서장인 경우
        if index==1:
            if task_map[index][1-(day % 2)]:
                completed_task_sum+=task_map[index][1-(day % 2)].popleft()
            

        #부서장, 말단 직원이 아닌 내부 직원인 경우
        else:
            #처리해야될 업무가 남은 경우 업무를 처리한다.
            if task_map[index][1-(day % 2)]:
                #처리한 작업을 올린다.
                task_map[index//2][index % 2].append(task_map[index][1-(day % 2)].popleft())

    
     #말단 노드에 대한 처리
    else:
        if tasks[index-2**h]:
            completed_task=tasks[index-2**h].popleft()
            task_map[index//2][index % 2].append(completed_task)
        return


    solution(day,index*2)
    solution(day,index*2+1)



if __name__ == "__main__":
    h,k,r=map(int,sys.stdin.readline().split())
    tasks=[deque(list(map(int,sys.stdin.readline().split()))) for _ in range(2**h)]
    #처리중인 작업의 목록을 담기 위한 배열
    task_map=[[deque(),deque()] for _ in range(2**h)]

    completed_task_sum=0
    for day in range(1,r+1):
        solution(day,1)
    print(completed_task_sum)