기차운행 Stack 응용

문제

A도시에서 출발한 기차는 B도시로 도착한다. 그런데 도로 중간에 T자형 교차로가 있어 출발한 기차의 도착 순서를 조정할 수 있다.

교차로에서는 다음과 같은 두 개의 작업을 합니다.

P(Push)작업: A도시에서 오는 기차를 교차로에 넣는다.

O(Out)작업: 교차로에 들어온 가장 최근 기차를 B도시로 보낸다.

만약 2 1 3 기차 번호 순으로 A도시에서 출발하더라도 B도시에는 T교차로를 이용하여 1 2 3 순으로 도착하게 할 수 있습니다.

그 작업 P, P, O, O, P, O 순으로 작업을 하면 B도시에 1, 2, 3 순으로 도착합니다.

1부터 N까지 번호를 가진 기차가 A도시에서 어떤 순으로 출발하든, B도시에 번호순으로 도착하도록 하는 교차로 작업을 출력합니다. 모든 기차는 교차로에 들어가야만 B도시로 갈 수 있습니다. 번호순서대로 도착이 불가능하면 impossible 이라고 출력합니다.

 

해결

교차로에 다음과 같이 6 1 2 5 4 3 의 기차가 들어간다고 가정하고 생각해보자.

A에서 출발한 기차는 무조건 stack을 거쳐야 한다. 즉 6을 입력함과 동시에 교차로 stack에 A가 저장되는 것이다.

이후 교차로에서 빠져나갈 수 있는 기차, 즉 stack의 꼭대기에 있는 기차가 순서에 맞는 기차인지 판단한다.

아래 상황에서 다음 기차는 1인데 stack의 꼭대기에는 6이 있으므로 6를 꺼내지 않은 채로 새 기차를 받는다.

이제 다음 기차인 1을 교차로 stack에 저장한다.

이후 다음 순서에 맞는 기차인지 판단한다.

다음 기차는 1이고 stack의 꼭대기에도 1이 있으니 기차를 꺼낸다.

기차 1번이 도착했으므로 다음 순서의 기차는 2가 된다.

남아있는 stack의 꼭대기가 다음 순서의 기차인지 확인한다.

다음 순서의 기차는 2인데 stack의 꼭대기에는 6이 있다. 그러므로 A에서 새 기차를 stack에 넣는다.

위와 같은 방법으로 기차 2도 stack에 넣었다가 B로 꺼낸다.

다음 순서의 기차는 2인데 stack의 꼭대기에는 6이 있다. 그러므로 A에서 새 기차를 stack에 넣는다.

다음 기차인 5가 stack에 저장된다. stack의 꼭대기가 된 5는 다음 순서인 3이 아니므로 다음 기차를 받는다.

다음 기차인 4가 stack에 저장된다. stack의 꼭대기가 된 4는 다음 순서인 3이 아니므로 다음 기차를 받는다.

stack의 꼭대기에 다음 순서의 기차인 3이 있으므로 3을 꺼낸다. 다음 순서의 기차는 4가 된다.

stack의 꼭대기에 다음 순서의 기차인 4가 있으므로 4를 꺼낸다. 다음 순서의 기차는 5가 된다.

stack의 꼭대기에 다음 순서의 기차인 5가 있으므로 5를 꺼낸다. 다음 순서의 기차는 6이 된다.

stack의 꼭대기에 다음 순서의 기차인 6가 있으므로 6을 꺼낸다. 모든 기차가 순서대로 꺼내졌다.

만약 기차가 1 3 6 4 5 2 순서로 들어간다면 어떨까?

1번 기차가 stack에 들어갔다가, 다음 순서 기차인 1이므로 빠져나온다

이제 다음 순서 기차인 2가 교차로에 들어올 때까지 교차로는 새 기차를 받을 것이다.

다음 순서 기차인 2가 stack에 들어왔을 때, 2가 빠져나가고 다음 순서 기차가 3이 된다.

하지만 다음 순서 기차인 3은 그 위 기차인 6 4 5에 가로막혀 꼭대기로 나올 수 없다.

또한 더이상 받을 수 있는 새 기차도 없다.

즉, 더이상 새 기차를 받을 수 없는 상태에서 교차로가 비워지지 않았다면, 그것은 기차를 순서대로 빼내는 것이 불가능한 상태이다.

이 경우 impossible을 출력한다.

따라서 다음과 같이 코드 구현이 가능하다.

 

코드 구현

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(void)
{
	int nTrainCount; //몇 대의 기차가 들어올 것인가 입력
	cin >> nTrainCount; 

	stack<int> stCrossRoad; //교차로로 사용할 stack
	vector<char> vecOutput; //기차의 P, O 정보를 저장할 vector
	int nNextNumber = 1; //다음 순서의 기차 번호, 1부터 시작해 하나씩 증가한다

	for (int i = 0; i < nTrainCount; i++) //입력받은 기차 수 만큼 기차가 들어온다
	{
		int nTrainNumber;
		cin >> nTrainNumber; //다음에 들어올 기차의 번호를 입력

		stCrossRoad.push(nTrainNumber); //들어온 기차는 무조건 교차로에 넣어져야 한다
		vecOutput.push_back('P'); //기차가 넣어졌으므로 문자열 P 추가

		//교차로 꼭대기에 있는 기차가 다음 순서 기차와 같은지 판정한다
		//교차로 꼭대기에 있는 기차가 다음 순서 기차와 같다면 stack에서 꺼내고 새로 꼭대기가 된 기차를 다시 판정한다
		//교차로 꼭대기에 있는 기차가 다음 순서 기차가 아니라면 반복문을 빠져나와 다음 기차를 받는다
		//모든 기차가 빠져나가 교차로가 비었다면 반복문을 빠져나와 다음 기차를 받는다
		while (true) 
		{
			if (stCrossRoad.empty()) //교차로가 비었다면 다음 기차를 받는다
				break;
			if (stCrossRoad.top() == nNextNumber) //교차로 꼭대기에 다음 순서 기차가 있다면 stack에서 꺼낸다
			{
				stCrossRoad.pop();
				vecOutput.push_back('O');
				nNextNumber++; //다음 기차 순서를 1 늘려주고 다시 새 꼭대기와 비교한다
			}
			else
				break; //교차로 꼭대기에 다음 순서 기차가 없다면 반복문을 중단하고 새 기차를 받는다
		}
	} //A에 있는 기차가 바닥나면 판정을 종료한다

	//만약 A에 있는 모든 기차를 받았는데도 교차로가 비워지지 않았다면 불가능한 것이다
	if (!stCrossRoad.empty())
		cout << "impossible" << endl;
	else
	{
		//교차로가 비워졌다면 성공한 것이니 입출력 결과를 출력한다
		for (int i = 0; i < vecOutput.size(); i++)
			cout << vecOutput[i] << " ";
	}

	return 0;
}

 

테스트

문제 제공 예시

위에서 든 예시

위에서 든 불가능 예시