2001년 가을학기 문제해결기법 - 문제 2

전화 수신 전환

우리 컴퓨터 회사는 직원이 출장이나 휴가 등으로 출근하지 않을 때 전화가 걸려오면, 다른 직원의 전화기에 벨이 울려서 전화를 받을 수 있도록 하는 □자동 수신 전환□ 기능을 이용하고 있다. 직원은 출근하지 않을 때는 걸려온 전화가 자동 수신 전환이 되도록 수신 전환하려는 전화번호를 입력한다. 다음에 출근하면 자신의 전화에 설정된 수신 전환을 해제한다.

회사 내에 있는 전화 교환기는 어떤 전화번호가 다른 번호로 수신전환 되어있는지 리스트를 보관하고 있다. 문제는 어떤 번호로 전화가 걸려왔을 때, 어느 전화기 벨을 울려야하는지를 결정하는 프로그램을 작성하는 것이다. 회사 내에서는 사용하는 전화번호는 모두 4자리이고, 전화 번호 0000은 특별한 목적으로 사용하기 위해서 남겨두기로 한다.

예를 들어서 3366번으로 걸려온 전화는 3366번 전화가 수신 전환되어 있지 않다면, 당연히 3366번 전화기 벨이 울려야 한다. 그러나 3366번이 3356번으로, 그리고 3356은 0154로 수신 전환되어 있다면, 3366으로 걸려온 전화는 수신 전환되어서 결국 0154번 전화기 벨이 울려야 할 것이다.

3366번은 3356으로, 3356은 0154로, 그리고 0154가 다시 3366으로 수신 전환되어 있다면 이들 번호로 걸려온 전화는 영원히 수신 전환되어 버리는 문제가 발생한다. 이런 경우는 0000번 전화기 벨이 울려서 전화를 받을 수 있도록 한다. 0000번 전화는 다른 전화를 수신 전환할 수 없다.

프로그램명은 phone.c(phone.cpp)라고 하고 실행 파일명은 phone.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫줄에는 걸려온 전화번호가 입력된다. 전화번호는 십진수로 4자리가 주어진다. 둘째 줄부터 마지막 줄까지는 한 줄에 전화번호의 쌍이 하나씩 주어진다. 전화번호의 쌍 xxxx, yyyy가 의미하는 것은 xxxx번 전화가 yyyy로 수신전환 되어 있다는 것을 말한다. xxxx번 전화가 yyyy와 zzzz로 동시에 수신 전환될 수는 없음에 주의한다. 입력 파일에는 콤마가 없고, 두 전화번호 사이에 빈칸이 하나 있다. 전화번호의 쌍은 1,000개를 넘지 않는다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 줄에 벨이 울려야할 전화기의 전화번호를 출력한다.

입력과 출력의 예

INPUT.TXT

3366

3366 3356

3356 0154

0101 1010

OUTPUT.TXT

0154