17223번 - 해시그래프

네트워크 상에서 유저들이 중앙 서버를 거치지 않고 통신할 때 문제시되는 점 중에 하나는 각 통신의 순서, 즉 '누가 먼저 통신을 했는지'이다. 통신의 순서를 명확하게 정의하는 것은 금전거래와 같이 순서의 혼동이 치명적으로 작용하는 시스템에서 매우 중요하다. 이 문제를 위해 제시된 해결책 중 '해시그래프'라는 자료구조가 있다. 설명에 앞서 본 문제는 Baird의 'Hashgraph consensus' 학술논문에 있는 개념 중 일부를 가져온 것임을 밝힌다. (Baird, Leemon. "The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance." Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep. (2016).)

해시그래프는 N명의 유저들 사이에서 "누가 누구에게 무엇을 어떤 순서로" 통신했는지 N의 너비에서 단방향으로 자라나는 그래프의 형태로 기록하는 자료구조이다. 이때 그래프의 정점은 이벤트라고 불리며 거래 정보 따위가 들어있다. 간선은 송신자의 마지막 이벤트와 수신자가 생성한 이벤트를 연결한다.

쉬운 이해를 위해 A, B, C, D 4명의 유저가 통신하는 해시그래프의 그림을 보자.

위 그림에서 네 명의 유저 A, B, C, D는 모두 첫 이벤트 A1, B1, C1, D1을 가지고 시작한다.

가장 먼저 B가 D에게 통신하여 이벤트 1을 생성한다. 이벤트 1은 B와 D의 마지막 이벤트인 B1, D1에 대한 정보를 담고 있다. 이 순간 A와 C는 이벤트 1의 존재를 알지 못한다. D가 B에게 통신하여 이벤트 2를 생성하고, B가 A에게 통신 함으로써 A가 이벤트 3a를 생성하는 순간에 비로소 A는 이벤트 3a로부터 이벤트 2를 거슬러내려가서 이벤트 1의 존재를 알 수 있게 된다. 이처럼 각각의 이벤트는 송신자/수신자의 마지막 이벤트 정보를 담고 있기 때문에 두 유저 A가 B에게 통신한다는 것은 A가 알고 있는 모든 통신 기록들을 B에게 전달한다는 의미이다.

한 편 이벤트 1, 2, 3a 사이에는 선후관계가 있기 때문에 순서가 명확하다. 하지만 3a, 3b, 3c와 같은 이벤트들의 순서는 쉽게 정하기 힘들다. 이러한 이벤트들의 선후관계는 '더 많은 유저들에게 더 빠르게 퍼지는 이벤트'를 먼저 일어난 이벤트로 정의한다. 해시그래프에서는 이 선후관계를 수학적으로 엄밀하게 정의하기 위해 복잡한 개념과 정리를 동원하지만 본 문제에서는 간단히 기본적인 개념만 알아보도록 하자.

• 3a와 2, 3a와 B1처럼 두 이벤트 사이에 선후관계가 존재한다면 3a는 2를(B1을) 볼 수 있다(x can see y)고 한다. 역은 x = y 일 때만 성립한다.

해시그래프는 이벤트 사이에 존재하는 이 "see"라는 개념과 추가적인 몇 가지 개념들을 이용해 모든 이벤트의 순서를 정의할 수 있음을 수학적으로 증명한다.

해시그래프와 두 이벤트가 주어졌을 때, 한 노드가 다른 노드를 볼 수 있는지 확인하는 프로그램을 작성해보자

첫째 줄에 유저 수 N(2 ≤ N ≤ 100)과 해시그래프 상에서 일어난 모든 통신 이벤트의 수 M(1 ≤ M ≤ 10,000)을 입력한다. (송신자가 없는 각 유저의 첫 이벤트는 제외)

두 번째 줄부터 M개의 줄에 걸쳐 i 유저가 j 유저에게 통신했다는 정보를 입력한다. (0 ≤ i, j ≤ N-1)

M+2번째 줄에는 A유저의 p번째 이벤트, B유저의 q번째 이벤트를 입력한다. (0 ≤ A, B ≤ N-1) p, q는 각각 A와 B가 실제로 가지고 있는 이벤트에 대한 입력값만 주어진다.

0번째 이벤트는 각 유저가 처음 생성한, 아무 유저에게도 통신 받지 않는 처음의 이벤트(사진 예시에서 A1, B1, C1, D1)를 의미한다고 하자.

A유저의 p번째 이벤트가 B유저의 q번째 이벤트를 볼 수 있다면 1을, 없다면 0을 출력한다.