그래프에서 간선 가중치의 bitwise or이 최소가 되는 경로

E - Minimum OR Path

E - Minimum OR Path

 

 

무방향 연결그래프에서 1번부터 N번까지 가는 단순 경로들의 모든 가중치들의 bitwise or의 최솟값을 구하는 문제

 

단순 경로는 어떤 정점을 두번이상 방문하지 않는 경로를 말한다.

 

1 > 2 > 3 > 4 > 5는 단순 경로

 

1 > 2 > 3 > 2 > 3 > 4 > 5는 2번 3번을 2번 방문했으므로 단순 경로가 아니다.

 

---------------------------------------------------------------------------------------------------------------------------------------

 

수들을 bitwise or을 한다면..?

 

두 수 a,b 를 이진수로 나타내고 각 비트를 비교해서 0과 0이 만나면 0, 1과 0이 만나면 1, 1과 1이 만나면 1

 

모든 가중치들을 bitwise or을 해야하므로, 여기서 중요한 것은 수들을 bitwise or을 하다가, k번째 비트가 1이 되는 순간

 

이 k번째 비트는 앞으로는 절대로 0이 될 수 없다는 것

 

지나는 경로들의 가중치들의 bitwise or이 최소가 될려면 어떻게 해야할까?

 

최상위 비트들이 0이 될수록 최소가 될 수 있다.

 

간선의 가중치가 2^30보다 작기 때문에 bitwise or을 해도 이진수로 나타냈을때 비트 수들은 최대 30자리이다.

 

따라서 먼저 x = 2^30-1부터 시작한다.

 

즉, 30자리를 모두 1로 채운 상태에서 시작

 

x = 11111111111111111111111111111111111....1111111

 

k = 29,28,27,....,0으로 시작해서 최상위 비트 29번째 비트부터 시작해서 최하위 비트로 순회하기 시작

 

k번째 비트를 0으로 만든다.

 

즉, x' = x - 2^k으로 하면 x의 k번째 비트를 0으로 바꿀 수 있다.

 

이제 모든 edge (u,v,w)를 순회해서 x'에 w를 bitwise or 했을때, x' 그대로 될 수 있다면 그러한 edge를 사용한다는 뜻에서 union한다.

 

x' | w = x'이라는 것은 무슨 뜻인가? 

 

해당 w는 k번째 비트를 1로 만들지 않는다는 뜻이다.

 

union이 끝나고 나서, 1번과 n번이 서로 같은 그룹이 되는지를 판단한다.

 

1번의 parent와 n번의 parent를 find로 찾아서, 두 parent가 서로 다르다면, 1번에서 n번까지 도달할 수 없다는 뜻이다.

 

따라서, k번째 비트를 0으로 만드는 간선들로는 1번에서 n번까지 도달할 수 없다.

 

즉, 1번부터 n번까지 도달하기 위해서는 k번째 비트를 1로 만드는 어떤 간선 w를 반드시 사용해야한다는 뜻이다.

 

다시 x = x' + 2^k로 갱신

 

그런데 두 parent가 서로 같다면 1번에서 n번까지, union을 위해 사용한 간선 w만으로 도달할 수 있다는 뜻이다.

 

이는 k번째 비트를 0으로 만드는 간선들로 1번에서 n번까지 도달할 수 있다는 뜻이므로, 

 

x = x'으로 갱신

 

이를 k = 29,28,27,...,0 순으로 반복해서 x값을 출력하면 답

 

def find(x):
    
    if parent[x] != x:
        
        parent[x] = find(parent[x])
    
    return parent[x]

def union(a,b):
    
    if parent[a] > parent[b]:
        
        parent[a] = b
    
    else:
        
        parent[b] = a

n,m = map(int,input().split())

edge = []

for _ in range(m):
    
    u,v,w = map(int,input().split())
    edge.append((u,v,w))

x = 2**30-1

for k in range(29,-1,-1):
    
    x = x - (2**k)

    parent = [i for i in range(n+1)]

    for u,v,w in edge:
        
        if (x | w) == x:
            
            u = find(u)
            v = find(v)
            union(u,v)
    
    u = find(1)
    v = find(n)
    
    if u != v:
        
        x = x + (2**k)

print(x)