고속버스 노선 > 문제은행

본문 바로가기


실전대비 Level5

1460 : 고속버스 노선

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 3 회    시도횟수: 85 회   



세 국가 A, B, C는 서로 국경을 마주하고 있으며, 각 국가에는 N개의 도시들이 있다. 이들 도시들에 대하여 국경을 통과하는 고속버스 노선을 N개 만들려고 한다. 전체 3N개의 도시들 중에서 2N개의 도 시들은 노선의 출발지 또는 도착지로 하고, 나머지 N개의 도시들은 어떤 노선의 중간 경유지가 되도록 고속버스 노선을 정하려고 한다. N개의 각 노선의 (출발지, 도착지)는 미리 주어져 있으며, 각 노선의 출발지와 도착지는 서로 다르다. 이때, 정하고자 하는 노선들은 다음 조건들을 모두 만족해야 한다.

 

(1) 출발지 또는 도착지가 아닌 도시는 임의의 노선의 중간 경유지가 될 수 있고, 반드시 어떤 노선의 중간 경유지로 포함되어야 하며, 하나의 노선에만 포함될 수 있다.
(2) 하나의 노선은 2개 이하의 중간 경유지를 갖는다. 노선에 중간 경유지를 포함할 때, 이 중간 경유 지가 속한 국가는 출발지나 도착지가 속한 국가와는 달라야 한다. 그리고 노선의 중간 경유지가 2개인 경우에 이들 두 경유지는 모두 같은 국가에 속할 수 없다. (그러므로 출발지와 도착지가 서 로 다른 국가에 속하는 노선은 많아야 1개의 중간 경유지만 가질 수 있다.)
(3) 출발지와 도착지가 같은 국가에 속한 노선은 반드시 1개 이상의 중간 경유지를 포함해야 한다. 각 도시의 이름은 국가이름과 번호로 나타낸다 (1 ≤번호 ≤N). A1은 국가 A의 1번 도시의 이름이고, B3은 국가 B의 3번 도시의 이름이다. 여기서 국가이름과 번호 사이에는 공백이 없다.
예를 들어, 각 국가에 3개의 도시가 있다 하자. 그리고 세 노선의 출발지, 도착지가 각각 (A1, B1), (A2, A3), (B2, C2)라 하자. 그러면 세 개의 노선을 다음과 같이 만들 수 있다.

 

노선 1: A1→C1→B1
노선 2: A2→B3→C3→A3
노선 3: B2→C2

 

출발지와 도착지의 쌍이 N개 주어진 경우, 위의 조건들을 만족하는 고속버스 노선들을 항상 정할 수 있다. 이러한 노선들을 출력하는 프로그램을 작성하시오. 만약 위의 조건들을 만족하는 고속버스 노선들 의 집합이 여러 개일 경우 임의의 하나만 출력하면 된다.


첫째 줄에는 도시들의 개수를 나타내는 정수 N(1≤N≤50,000) 이 주어진다.
둘째 줄부터 N + 1번째 줄까지 각 줄에 노선의 출발지와 도착지가 공백을 사이에 두고 주어진다.


첫째 줄부터 N번째 줄까지 입력에 주어진 노선 순서대로 각 줄에 해당 노선에 포함되는 도시들의 이름을 출발지부터 도착지까지 순서대로 출력한다. 
한 노선에 속 하는 도시이름과 도시이름 사이에는 공백을 하나 둔다.

[Copy]
3
A1 B1
A2 A3
B2 C2
[Copy]
A1 C1 B1
A2 B3 C3 A3
B2 C2





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.