회로 설계

마이크로칩 설계는 계산 복잡도 이론에서 논리 회로를 연구하는 것과 다르다. 칩을 만들 때는 논리 소자의 입력이 바뀐 뒤 소자가 반응해 출력이 바뀌기까지 걸리는 시간 지연과, 전기 신호가 전선을 따라 전파되는 속도가 유한하다는 점을 함께 고려해야 한다.

논리 회로는 방향이 있는 비순환 그래프이다. 각 정점은 입력, 출력, 논리 소자 중 하나이다. 입력은 들어오는 간선이 없고 나가는 간선을 여러 개 가질 수 있다. 출력은 나가는 간선이 없고 들어오는 간선이 정확히 하나이다. 이 문제에서는 or, and, not 세 종류의 논리 소자를 다룬다. or와 and 소자는 들어오는 간선이 정확히 두 개이고 나가는 간선은 몇 개든 가질 수 있다. not 소자는 들어오는 간선이 정확히 하나이고 나가는 간선은 몇 개든 가질 수 있다.

그래프에 간선 $uv$가 있으면 $u$를 $v$의 선행 정점이라고 한다.

각 정점은 0 또는 1의 논리값을 가진다. 입력 정점의 값은 회로의 매개변수, 즉 회로에 주어지는 입력 데이터이다. 나머지 정점의 값은 다음과 같이 계산한다.

출력 정점은 선행 정점을 정확히 하나 가지며, 출력의 값은 그 선행 정점의 값과 같다.

or 소자는 선행 정점 중 적어도 하나가 1이면 1이다.

and 소자는 두 선행 정점이 모두 1이면 1이다.

not 소자는 선행 정점이 0이면 1이다.

그래프가 비순환이므로, 입력 값이 정해지면 이 정의로 모든 정점의 값이 하나로 정해진다.

어떤 입력의 값이 바뀌면 다른 정점의 값도 바뀔 수 있다. 그런데 여러 입력의 값이 동시에 바뀌면, 입력마다 변화가 전달되는 시간 차이 때문에 회로의 동작이 어긋날 수 있다. 신호가 전선을 따라 전파되는 속도가 유한한 것도 같은 효과를 낳는다. 이런 효과로 일부 정점이 잠시 잘못된 값을 가질 수 있으며, 이를 기생 값(parasitic value)이라고 한다.

예를 들어 아래 그림의 회로를 보자.

입력이 $(0, 1)$에서 $(1, 0)$으로 바뀔 때, 첫 번째 입력이 0에서 1로 바뀌는 것이 두 번째 입력이 1에서 0으로 바뀌기 전에 일어나면 위쪽 출력이 잠시 1을 가질 수 있다. 그러나 처음과 끝의 입력 값에서 위쪽 출력은 모두 0이어야 한다.

전선의 지연은 더 놀라운 효과를 낳는다. 아래 그림의 회로를 보자.

언뜻 보면 기생 값은 생길 수 없을 것 같다. 어느 입력이 먼저 바뀌든 출력은 0이기 때문이다. 하지만 그렇지 않다. 입력이 $(0, 1)$에서 $(1, 0)$으로 바뀐다고 하자. 두 입력은 동시에 바뀌지만, 위쪽 입력에서 and 소자까지의 거리는 매우 짧고 or 소자까지의 거리는 길다. 반대로 아래쪽 입력에서 and 소자까지의 거리는 매우 길고 or 소자까지의 거리는 짧다. 그러면 and 소자는 위쪽 입력의 변화를 아래쪽보다 먼저 알게 되어 1로 바뀐다. 마찬가지로 or 소자는 아래쪽 입력의 변화를 위쪽보다 먼저 알게 되어 0으로 바뀐다. not 소자의 값은 1이 되고, 마지막으로 가장 오른쪽 and 소자와 출력이 1로 바뀐다. 이후 바뀐 정보가 점차 모든 소자에 전달되고, 각 소자는 올바른 값으로 바뀐다.

이 과정을 정식화하기 위해, 각 간선은 시작 부분과 끝 부분에서 서로 다른 값을 가질 수 있다고 가정한다. 간선 시작 부분의 값이 바뀌면, 간선 끝 부분의 값은 즉시 바뀌지 않고 일정 시간이 지난 뒤에 바뀔 수 있다.

회로의 전환 과정에서는 다음 사건이 어떤 순서로든 일어날 수 있다.

• 회로의 입력 하나가 초기 값에서 최종 값으로 바뀐다. 새 값은 이 정점에서 나가는 모든 간선의 초기 값이 된다.
• 들어오는 간선의 최종 값과 맞지 않는 값을 가진 소자 또는 출력 하나가 올바른 값으로 바뀐다. 새 값은 이 정점에서 나가는 모든 간선의 초기 값이 된다.
• 간선 하나의 최종 값이 그 간선의 초기 값과 같아진다.

모든 입력이 최종 값으로 바뀌고, 모든 간선의 초기 값과 최종 값이 일치하며, 모든 정점의 값이 올바르면 전환이 끝난다.

각 출력에 대해 초기 값을 $i$, 최종 값을 $f$라고 하자. 전환 전과 각 사건이 일어난 뒤 이 정점의 값을 살펴본다. 어떤 사건 이전에는 값이 $i$와 같고, 그 뒤 전환이 끝날 때까지 값이 $f$와 같으면 이 출력은 안전(safe)하다. 특히 $i = f$이면 출력 값은 전혀 바뀌면 안 된다. 사건이 일어나는 가능한 순서 중 하나라도 이 조건을 만족하지 않으면 이 출력은 안전하지 않다(unsafe).

주어진 논리 회로와 그 전환을 바탕으로, 각 출력이 안전한지 판별하라.

첫 줄에 정점의 개수 $n$이 주어진다($2 \le n \le 1200$). 다음 $n$개의 줄은 정점을 설명한다. 각 줄은 정점의 종류로 시작하며, 종류는 in, out, and, or, not 중 하나이다.

• in이면 0 또는 1인 정수 두 개가 주어진다. 이 입력의 초기 값과 최종 값이다.
• out 또는 not이면 선행 정점의 번호 하나가 주어진다.
• and 또는 or이면 선행 정점의 번호 두 개가 주어진다.

정점은 입력에 주어진 순서대로 1부터 $n$까지 번호가 매겨진다. 선행 정점의 번호는 항상 그 정점의 번호를 넘지 않는다.

각 출력 정점에 대해 한 줄을 출력한다. 번호가 k인 출력이 안전하면 Node k is safe.를, 안전하지 않으면 Node k is not safe.를 출력한다.