[백준] 1033 칵테일

문제 주소 : www.acmicpc.net/problem/1033

1033번: 칵테일

문제 확인

 

a -> b 관계식이 있을 때 b -> c 관계식이 a에게 영향을 미치므로 그래프 탐색 문제입니다.

 

풀이

 

문제에서 주어진 n개의 vertex와 n-1개의 edge를 가지면서 n개의 vertex에 대한 모든 관계식을 나타내기 위해서는 사이클이 존재할 수 없습니다. 따라서 입력받을 시 edge를 작성하면서 비율을 맞춰가면 됩니다.

 

최대 공약수, 최소 공배수를 활용해 곱할 값을 찾아냅니다.

현재 vertex a의 값을 a_val, vertex b 값을 b_val로 두고 비율을 p, q로 둡니다.

먼저 비율을 맞추기 전에 같은 값으로 만들어 주기 위해 최소공배수로 만들어 줍니다. 이때 서로 곱해야 할 값은 a : b/gcd, b : a/gcd 가 됩니다. 그 후 p, q를 각각 곱해주면 다음과 같아집니다.

a_val = a_val * b / gcd * p

b_val = b_val * a / gcd * q

여기서 주의해야 할 점은 vertex a와 연결된 다른 점들 또한 b / gcd * p 값을 곱해주고 b와 연결된 점들 또한 곱해주어야 전체 비율이 맞춰지게 됩니다. dfs(a, a_mod / g); dfs(b, b_mod / g); 를 통해 간단하게 구현해 줍니다.

그 후 두 점들을 연결하고 이러한 과정을 반복하면 됩니다.

 

코드

#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
typedef struct vertex {
    int val;
    vector<int>edge;
}vertex;
int n;
vertex vtx[10];
bool visited[10];
long gcd(long a, long b) {//최대 공약수, 최소 공배수 = a * b / gcd
    long r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
void dfs(int cur, int val) {
    visited[cur] = true;
    vtx[cur].val *= val;//비율 반영
 
    for (auto next : vtx[cur].edge)
        if (!visited[next])
            dfs(next, val);
}
int main() {
    
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, p, q;
        scanf("%d%d%d%d", &a, &b, &p, &q);
        if (!vtx[a].val)
            vtx[a].val = 1;
        if (!vtx[b].val)
            vtx[b].val = 1;//처음 방문한 경우
 
        int g = gcd(vtx[a].val, vtx[b].val);
        int a_mod = vtx[b].val / g * p, b_mod = vtx[a].val / g * q;//곱할 값 계산
        g = gcd(a_mod, b_mod);
        memset(visited, 0, sizeof visited);
        dfs(a, a_mod / g);//전체 반영
        dfs(b, b_mod / g);
 
        vtx[a].edge.push_back(b);//연결
        vtx[b].edge.push_back(a);
    }
    for (int i = 0; i < n; i++)
        printf("%d ", vtx[i].val);
}