인과성 검사
면접 대비시간 제한1초메모리 제한128 MB
여러 컴퓨터의 송수신 이벤트와 로컬 시간 순서가 주어질 때, 이 순서 제약이 사이클을 이루어 인과성을 위반하는지 판별합니다.
문제
분산 시스템에서는 인과성이 중요하다. 한 컴퓨터가 메시지를 보내고 다른 컴퓨터가 그 메시지를 받는다면, 실제 시간에서는 송신 사건이 수신 사건보다 먼저 일어나야 한다. 모든 컴퓨터가 하나의 전역 시계를 공유한다면, 수신 시각은 항상 송신 시각보다 클 것이다.
하지만 분산 시스템에는 그런 전역 시계가 없다. 각 컴퓨터는 서로 다른 자기 시계를 가지고 있고, 그 시계들은 서로 다른 속도로 흐를 수 있다. 확실히 말할 수 있는 것은 한 컴퓨터 안에서 나중에 일어난 사건은 이전 사건보다 항상 더 큰 시각을 가진다는 점뿐이다. 따라서 어떤 메시지가 한 컴퓨터의 시계로 50에 보내져 다른 컴퓨터의 시계로 40에 도착하는 일도 가능하다.
여러 메시지의 송신 시각과 수신 시각이 주어진다. 각 시각 데이터 집합마다, 메시지의 방향과 각 컴퓨터 내부의 시각 증가 순서가 인과성과 모순되는지 판정하라. 메시지를 따라 이동하고 같은 컴퓨터에서는 더 큰 시각으로만 이동했을 때 유향 순환이 생기면 인과성이 위반된 것이다.
입력
입력은 여러 개의 시각 데이터 집합으로 구성된다. 각 집합은 메시지 수 n으로 시작한다. 이어지는 n개의 줄에는 보내는 컴퓨터, 보낸 시각, 받는 컴퓨터, 받은 시각이 공백으로 구분되어 주어진다.
시각은 해당 컴퓨터의 시계로 측정한 정수이다. 컴퓨터는 대문자 한 글자로 나타낸다. 정수 0 하나만 있는 줄이 입력의 끝이다.
출력
각 시각 데이터 집합마다 한 줄을 출력한다. 인과성 위반이 없으면 OK, 위반이 있으면 Bad를 출력한다.