[문제 풀이 19] 코드 트리 - 구역마다 다른 드랍 아이템

구역마다 다른 드랍 아이템

 

• 문제 유형 : Greedy, Graph
• 사용언어 : Python
• 난이도 : 실버 4
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/different-area-drop-item?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

def solve(N, M, pairs):
    graph = {}

   
    for a, b in pairs:
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append(b)
        graph[b].append(a)

    print(graph)

  
    items = [0] * (N + 1)  

    # 모든 구역에 대해 아이템 할당
    for node in range(1, N + 1):
   
        available = {1, 2, 3, 4}
        if node in graph:

            for neighbor in graph[node]:

                if items[neighbor] in available:
                    available.remove(items[neighbor])
        # 사전 순으로 가장 앞선 아이템 선택
        items[node] = min(available)
    
 
    return ''.join(map(str, items[1:]))


N, M = map(int, input().split())
pairs = [map(int, input().split()) for _ in range(M)]

output = solve(N, M, pairs)
print(output)