Coding 공부

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
material_dict = {'-1':True}
# dict를 고정시키는게 문제
material_pay = [float('inf') for _ in range(10000)]
queue = deque()
for k in range(N):
    name,pay = input().split()
    material_dict[name] = k+1
    material_pay[k+1] = int(pay)
    queue.append(material_dict[name])



graph = defaultdict(list)


total_recipe_list = [input() for _ in range(M)]
recipe_cnt = defaultdict(int)
recipe_dict = defaultdict(list)
recipe_order = defaultdict(list)
total_recipe_list.sort()

for total_recipe in total_recipe_list:
    complete_name,arg = total_recipe.split('=')
    recipe = arg.split('+')
    if material_dict.get(complete_name):
        complete_idx = material_dict[complete_name]
    else:
        complete_idx = len(material_dict.keys())
        material_dict[complete_name] = complete_idx

    recipe_idx = (complete_idx,recipe_cnt[complete_idx])
    recipe_cnt[complete_idx] += 1
    temp_set = set()
    temp = defaultdict(int)
    for res in recipe:
        cnt,name = int(res[0]),res[1:]
        if material_dict.get(name):
            name_idx = material_dict[name]
        else:
            name_idx = len(material_dict.keys())
            material_dict[name] = name_idx
        if recipe_idx not in graph[name_idx]:
            graph[name_idx].append(recipe_idx)
        temp_set.add(name_idx)
        temp[name_idx] += cnt
    recipe_order[complete_idx].append(temp_set)
    recipe_dict[complete_idx].append(temp)

flag = True
        
total_len = len(material_dict) - 1
cnt = 0
while queue:

    name_idx = queue.popleft()
    if graph.get(name_idx):
        for next_idx,recipe_idx in graph[name_idx]:
            # 다시 들어왔을때 문제
            if name_idx in recipe_order[next_idx][recipe_idx]:
                recipe_order[next_idx][recipe_idx].remove(name_idx)


            if not len(recipe_order[next_idx][recipe_idx]):
                temp = 0

                for mat,val in recipe_dict[next_idx][recipe_idx].items():
                    temp += material_pay[mat]*val
                if material_pay[next_idx] > temp:

                    queue.append(next_idx)
                    material_pay[next_idx] = temp
                
if material_dict.get('LOVE'):
    result = material_pay[material_dict['LOVE']]
    if result == float('inf'):
        print(-1)
    elif result > 1000000000:
        print(1000000001)
    else:
        print(result)
else:
    print(-1)

이 문제는 여러번 틀렸던 문제였다.

풀면서 주의해야할 점은 다음과 같다.

처음에 주어지는 재료의 개수가 N의 최대가 50이라고 했지

모든 레시피에서 주어지는 재료의 개수가 50인게 아니다.

그래서 이걸 저장을 할때에는 넉넉하게해줘야한다.

두번째 여기서는 사이클같은 구조가 생길수 있다.

즉 위상정렬에서 한번 검사했던 노드이지만,

들어간 재료 중 하나가 최저값이 갱신이 되서, 현재 만들어지는 재료가 더 줄어둘수도 있다.

세번째 들어오는 입력에서 같은 재료가 여러번에 나뉘어서 들어 올수 있다.

네번째 같은 재료를 만드는 레시피가 여러종류가 있을 수 있다.

그래서 이 문제를 풀때 기본 컨셉은 다음과 같다.

각 완성재료를 만드는 전체 레시피들은 recipe_dict에 넣어줬다.

같은 완성재료를 만드는 방법이 여러개라면, recipe_cnt로 각 완성재료를 만드는 n번째 idx 이런식으로 구분을 해주었다.

그리고 위상정렬을 위해 order를 저장해주는 방식은

recipe_order[완성재료][레시피idx] 에 들어간 재료를 set으로 저장을 해주었다.

그리고 가장 중요한 그래프는 다음과 같이 저장을 해주었다.

graph라는 dictionary에 한 완성재료를 만드는 부품에 각각 (완성재료,완성재료를 만드는 레시피의 번호)를 저장시켜주었다.

그리고 material_dict은 재료명 대신 숫자로 관리하기 위해 만들어놨다.

material_pay는 각 재료를 만드는데 최소비용을 저장시켜놓은 리스트이다.

그러면 위상정렬을 어떻게 시작하면 되면

최초에 주어진 재료 N개를 queue에 넣어준다.

그리고 그 queue에서 하나씩 꺼내서

graph[name_idx]를 통해

이 재료로 만들 수 있는 레시피들에서 이 재료를 삭제시켜주었다.

이때 나중에 또 방문할 수 있으니, 있는지 확인을 하고 제거를 해준다.

그리고 이 recipe_order에 있는 set이 전부 사라져서 길이가 0 이면,

그때 queue에 들어갈수 있는지 확인해준다.

우리가 저장해놓은 recipe_dict을 이용해서 현재 재료들의 최저가로 만들었을때 나오는 비용을 계산한다.

비용을 계산한 후,  material_pay에 있는 값과 비교를 해서

최저가가 갱신이 되면 queue에 넣어준다.

그리고 이 반복문은 queue가 빌때까지 무한 반복해준다.

그러면 우리는 결과를 출력할때 두가지로 먼저 나눈다.

레시피와 재료에 아예 LOVE가 없을때, 그때는 -1을 출력해준다.

레시피와 재료에 있지만, 초기값인 float('inf')일때에는 -1을 출력해준다.

왜냐하면 어디선가 재료가 부족해서 LOVE에 아예 접근을 못한상태이기 때문이다.

그리고 1000만이 넘었을때에는 1000만1 그 외에는 재료값을 출력하게 해준다.

푼 사람들 코드 중에 제가 푼 코드보다 가독성이 좋고, 좋은 코드들이 있다.

가독성을 늘리는 방법은 중간에 제가했던 사전작업과 위상정렬을 동시에 해버리면된다.

어떤 상황에서 큐에 들어가는지와 어떤상황에서 종료를 해야하는지 파악하면 풀 수 있는 문제이다.

즉 들어온 입력들 전체를 while문을 돌리면서

단 한번도 최저값이 갱신된적이 없거나, 새로운 재료가 생기지 않았다면, 종료를 해주면 된다.

import sys
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

    for _ in range(P):
        x,y = map(int,input().split())
        graph[y].append(x)

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

이런 방식을 이용해서도 문제를 풀 수 있습니다.

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())


for tc in range(T):
    N = int(input())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 전년도 1등부터 ~ N등까지 팀 순서
    prev_order_team = list(map(int,input().split()))
    indegree = [0]*(N+1)
    indegree[0] = float('inf')
    for rank,team_num in enumerate(prev_order_team):
        indegree[team_num] = rank
        for low_team_num in prev_order_team[rank+1:]:
            graph[team_num][low_team_num] = 1

    M = int(input())
    new_indegree = indegree[:]
    for _ in range(M):
        a_team,b_team = map(int,input().split())
        if indegree[a_team] > indegree[b_team]:
            a_team,b_team = b_team,a_team

        # a_team이 상위권 b_team이 하위권 원래는
        graph[b_team][a_team] = 1
        graph[a_team][b_team] = 0
        new_indegree[a_team] += 1
        new_indegree[b_team] -= 1
    indegree = new_indegree[:]
    stack = deque()

    for team_num in range(1,N+1):
        if not indegree[team_num]:
            stack.append(team_num)
    result = []
    if len(stack) == 1:
        cnt = 0
        while cnt<N:
            if not len(stack):
                result = 'IMPOSSIBLE'
                break
            elif len(stack) > 1:
                result = '?'
                break

            cur_node = stack.popleft()
            result.append(cur_node)
            for next_node in range(1,N+1):
                if graph[cur_node][next_node]:
                    indegree[next_node] -= 1
                    if not indegree[next_node]:
                        stack.append(next_node)
            cnt += 1
    elif len(stack) == 0:
        result = 'IMPOSSIBLE'
    else:
        result = '?'
    if type(result) == list:
        print(*result)
    else:
        print(result)

이 문제는 최근에 풀었던 문제 중에서 문제를 이해하는데 가장 힘들었던 문제였다. 문제를 이해하고 보면,

쉽게 이해가 가능한 문제이다.

문제에 주어진 N개의 숫자는

앞에서부터 1등부터 N등까지를 표현한 것이다.

그리고 그 각 자리에 있는것이 1등을 한 팀 N_1  2등을 한 팀 N_2 이런식인것이다.

그러면 문제에 첫 예제로 주어진

5 4 3 2 1

1등은 5팀

2등은 4팀

3등은 3팀

4등은 2팀

5등은 1팀

이 된것이다. 그렇다는 것은 이걸 그래프적으로 표현을 하면 다음과 같다.

 다음 과 같이 표현을 할 수 있을 것이다.

5팀이 가장 루트 노드이고, 이 5팀을 지나가고 난뒤에 4팀 3팀 2팀 1팀을 순서적으로 할 수 있는것이다.

그러면 여기서 상대적인 등수가 바뀌었다는 것은

저 그래프에서의 순서가 뒤바뀐다는 것을 의미하게 된다.

그러면 첫번째 예제에선

2 4

3 4 라는 입력이 주어졌다.

그러면

빨갛게 동그라미 모양이 된 화살표가 반대로 가게 되는것이다.

즉 녹색화살표 처럼 반대로 표시가 바뀌게 된것이다.

그러면 이때의 순위는

5 -> 3->2->4->1 순서가 되는 것을 알 수 있다.

그래서 이 문제에서 중요한 것은

처음 입력이 주어졌을때 자기 등수보다 이하의 등수들에게 부모 자식 관계를 나타내느 그래프 간선을 그려준다.

그리고 난뒤에 m개의 상대적인 순위가 바뀌었다는 입력이 들어오면

서로원래의 rank를 확인해서

높은 랭크 -> 낮은 랭크로 연결되어있던 간선을 반대로 바꾸어주고,

우리가 간선을 들어온 개수를 세어놓은 indegree 수치를

낮은 순위는 1개를 줄여주고, 높은 순위는 1개를 높여주면 된다.

그리고 여기서 주의해야할 것은 바로 값을 바꾸면 바뀐 순위를 참조가 가능하므로,

복사된 배열에서 값을 변경시키고 나중에 옮겨줘야한다.

그리고 정상적인 위상정렬을 시행해주면 된다.

만약에 스택이 비게되면 사이클이 발생한 것이므로,  impossible을

스택에 길이가 2개이상이 된다는것은 같은 rank에 2개가 있게 되는 것이므로, ?를 출력하게 해주면 된다.

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())

    prev_rank = [0]*(N+1)
    current_rank = [0]*(N+1)
    arr = list(map(int,input().split()))
    for i in range(N):
        prev_rank[arr[i]] = i +1
        current_rank[arr[i]] = i + 1

    M = int(input())

    for _ in range(M):
        a_team,b_team = map(int,input().split())

        if prev_rank[a_team] > prev_rank[b_team]:
            current_rank[a_team] -= 1
            current_rank[b_team] += 1
        else:
            current_rank[a_team] += 1
            current_rank[b_team] -= 1

    result = [0]*(N+1)
    flag= False
    for team_num in range(1,N+1):
        if result[current_rank[team_num]]:
            flag = True
            break
        else:
            result[current_rank[team_num]] = team_num

    if flag:
        print('IMPOSSIBLE')
    else:
        print(*result[1:])

 이건 좀 더 간단한 풀이이다.

 하지만 이 풀이는 ?인 경우가 없다고 가정하고 푼 것이다.

import sys
from collections import deque

input = sys.stdin.readline


N,M = map(int,input().split())
graph = [set() for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
    pdN,*arr = list(map(int,input().split()))

    for i in range(pdN-1):
        x,y = arr[i],arr[i+1]
        if y not in graph[x]:
            graph[x].add(y)
            degree[y] += 1

stack = deque()
cnt = 0
result = []
flag = True

for i in range(1,N+1):
    if degree[i]==0:
        stack.append(i)
while cnt<N:
    if not stack:
        flag = False
        break
    node = stack.popleft()
    result.append(str(node))
    for next_node in graph[node]:
        degree[next_node] -= 1

        if degree[next_node] == 0:
            stack.append(next_node)
    cnt += 1

if flag:
    print('\n'.join(result))
else:
    print(0)

이 문제와 같은 경우 평범한 위상정렬이다.

여러명의 PD를 통해 앞에서부터, 하나씩 그래프에 SET으로 넣어주었다.

그리고 degree가 0인것들은 최초의 stack에 넣어주고 난뒤에 위상정렬을 구해주면서,

사이클이 발생할 시, 음악프로그램을 구할 수 없는 것이므로, 그때 flag로 분기 처리를 해주었다.

그리고 stack에 나온순서대로 result에 넣어주고 출력을 해주었다.

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int,input().split())
recipe_dict = {}
next_node_list = [set() for _ in range(N+1)]
for _ in range(M):
    input_list = list(map(int,input().split()))
    recipe = input_list[1:-1]
    liquid_number = input_list[-1]
    recipe.sort()
    if recipe_dict.get(liquid_number):
        recipe_dict[liquid_number].append([set(recipe),input_list[0]])
    else:
        recipe_dict[liquid_number] = [[set(recipe),input_list[0]]]

    for num in recipe:
        next_node_list[num].add(liquid_number)

L = int(input())
own_liquid = list(map(int,input().split()))
possible_list = [False]*(N+1)
result = set()
for num in own_liquid:
    possible_list[num] = True
    result.add(num)
queue = deque(own_liquid)
while queue:
    cur_num = queue.popleft()

    next_nodes = next_node_list[cur_num]

    for next_node in next_nodes:
        if possible_list[next_node]:
            continue
        for ind in range(len(recipe_dict[next_node])):
            recipe = recipe_dict[next_node][ind][0]
            cnt = recipe_dict[next_node][ind][1]

            if cur_num in recipe:
                cnt -= 1
                recipe.remove(cur_num)
                recipe_dict[next_node][ind][0] = recipe
                recipe_dict[next_node][ind][1] = cnt
                if cnt == 0:
                    possible_list[next_node] = True
                    queue.append(next_node)
                    result.add(next_node)


print(len(result))
result = sorted(list(result))
print(*result)

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
recipe_remain_cnt = []
liquid_number = []
next_recipe_array = [[] for _ in range(N+1)]
for i in range(M):
    k,*recipe,r = map(int,input().split())

    recipe_remain_cnt.append(k)
    liquid_number.append(r)

    for num in recipe:
        next_recipe_array[num].append(i)


L = int(input())
own_liquid = list(map(int,input().split()))
result = set(own_liquid)


while own_liquid:
    cur_num  = own_liquid.pop()
    for recipe_idx in next_recipe_array[cur_num]:
        recipe_remain_cnt[recipe_idx] -= 1
        if recipe_remain_cnt[recipe_idx] == 0 and liquid_number[recipe_idx] not in result:
            own_liquid.append(liquid_number[recipe_idx])
            result.add(liquid_number[recipe_idx])

print(len(result))
result = sorted(list(result))

print(*result)

import sys

input = sys.stdin.readline

from collections import deque

N, M = map(int,input().split())

graph = [{} for _ in range(N+1)]
parents_cnt = [0]*(N+1)
result = []
visited = [True]*(N+1)
for _ in range(M):
    A,B = map(int,input().split())
    graph[A][B] = 1
    parents_cnt[B] += 1

que = deque()
for i in range(1,N+1):
    if not parents_cnt[i]:
        que.append(i)
for i in range(N):
    x = que.popleft()
    result.append(x)

    for next_node in graph[x]:
        parents_cnt[next_node] -= 1
        if parents_cnt[next_node] == 0:
            que.append(next_node)
print(*result)

m.blog.naver.com/ndb796/221236874984

위상정렬에 관련된 처음 보는 문제였고, 순서가 정해진 작업을 차례대로 작업할 순서를 정할때 쓰는 알고리즘이라는 것을 알았다.

이 알고리즘에 대해 더 공부하고, 기본 틀을 완성시켜놔야할것 같다.