[백준] 1033번 : 칵테일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1033번: 칵테일

 

1. 문제 설명

2. 풀이과정

해당 문제에서 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 한 것으로 보아 해당 문제를 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.

위 내용을 바탕으로 임의의 시작점에서 DFS를 진행하며 정답을 찾으면 해결할 수 있다.

필요한 재료의 질량을 모두 더한 값이 최소가 되어야 하므로 DFS 과정에서 유클리드 호제법을 활용해 비율들의 최소 공배수와 최대 공약수를 구해 정답에 활용한다.

 

인접 리스트를 이용해 각 재료의 비율 자료를 그래프로 구현한다.

데이터를 입력받아 저장할 때마다 비율과 관련된 수들의 최소 공배수와 최대 공약수를 업데이트한다.

임의의 시작점에 최소 공배수의 값을 저장하고 해당 시작점에서 DFS로 탐색을 수행하며 각 노드의 값을 이전 노드의 값과의 비율 계산을 통해 계산하고 저장한다.

각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력한다.

 

슈도코드

1. N(재료의 개수) 입력받기
2. graph(인접 리스트로 그래프 구현)
3. lcm(최소 공배수)
4. 최대 공약수를 구할 함수 구현 gcd(a, b):
   1. if (b가 0이면): a가 최대 공약수
   2. else: gcd(작은 수, 큰 수 % 작은 수)
5. for 비율 정보 N - 1개만큼 반복:
   1. a, b, p, q 입력받기
   2. 인접 리스트에 각 노드별 비율 정보를 저장
   3. 최소 공배수 (두 수의 곱 / 두 수의 최대 공약수) 업데이트
6. visited(DFS를 탐색할 때 탐색 여부 저장 리스트)
7. 탐색 함수 구현 DFS(v):
   1. visited 리스트에 현재 노드의 방문 기록
   2. for 현재 노드의 연결 노드 하나씩:
      1. next(다음 연결 노드)
      2. if (다음 연결 노드가 방문하지 않은 노드이면):
         1. 다음 노드의 값 = 현재 노드의 값 * 비율
         2. DFS(다음 노드)
8. li(각 노드의 값을 저장할 리스트)
9. 0번 노드에 최소 공배수의 값을 저장
10. 0번 노드에서 DFS 탐색
11. mgcd(li 리스트 값들의 최대 공약수)
12. for 1 ~ N: DFS를 이용해 업데이트된 li 리스트 값들의 최대 공약수를 구함
13. li 리스트의 각 값을 최대 공약수로 나눈 결과 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

graph = [[] for _ in range(N)]
lcm = 1

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
    
for _ in range(N - 1):
    a, b, p, q = map(int, sys.stdin.readline().split())
    graph[a].append([b, p, q])
    graph[b].append([a, q, p])
    lcm *= (p * q // gcd(p, q))

visited = [True] * N

def DFS(v):
    visited[v] = False
    for i in graph[v]:
        next = i[0]
        if (visited[next]):
            li[next] = li[v] * i[2] // i[1]
            DFS(next)

li = [0] * N
li[0] = lcm
DFS(0)

mgcd = li[0]
for i in range(1, N):
    mgcd = gcd(mgcd, li[i])

for i in range(N):
    print(int(li[i] // mgcd), end=' ')