문제

Sogang ICPC Team에서는 학회원들을 돕기 위해 Sogang Program Consulting Team(이하 SPC Team)을 만들었다. SPC Team은 학회원들과 화목하게 지내게 될 날만을 상상하며 에러가 발생한 코드를 무료로 디버깅해주는 컨설팅을 바로 시작했다.

그러던 어느 날, 기세등등했던 SPC Team의 모두를 당황시킨 코드가 등장했다. 아무리 봐도 정상적인 코드인데, 원하는 데이터를 얻을 수 없었던 것이다. 하지만 포기를 모르는 SPC Team은 계속해서 디버깅을 시도한 끝에, 한 번에 여러 줄의 명령이 실행되고 있었다는 사실을 알게 되었다! 이 상황을 이해하기 위해 다음 예시를 살펴보자.

1: WRITE A TO B
2: WRITE B TO C
3: READ B
4: READ C
5: EXIT

위 코드는 문제가 된 학회원의 코드이다. 명령어가 순서대로 실행되면 전혀 문제가 없을 코드지만, 줄 1–4가 동시에 실행된다면 문제가 생긴다. 메모리 A에서 메모리 B로 데이터가 옮겨지지도 않았는데 두 번째 줄이 실행되면, 메모리 C에 무슨 데이터가 들어갈지 알 수 없다. 이러한 문제를 확인한 SPC Team은 다음과 같이 컨설팅을 해 주었다.

1: WRITE A TO B
2: WAIT
3: WRITE B TO C
4: WAIT
5: READ B
6: READ C
7: EXIT

위와 같이, 중간에 WAIT를 삽입하여 WRITE A TO B와 WRITE B TO C가 동시에 실행되는 것을 막아준다면, 메모리 C에 어떤 데이터가 들어갈지 명확해진다! 위 코드에 대한 컨설팅을 끝마친 SPC Team은 문제가 발생할 수 있는 경우를 다음과 같이 세 가지로 분류했다.

• READ with WRITE
  • WRITE A TO B와 READ B가 동시에 실행되면, 메모리 B의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
  • WRITE A TO B와 WRITE B TO C가 동시에 실행되면, 메모리 C의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
• WRITE with WRITE
  • WRITE A TO C와 WRITE B TO C가 동시에 실행되면, 메모리 C의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
  • WRITE A TO B와 다른 WRITE A TO B가 동시에 실행되는 것은 문제가 없지만, 프로그램의 안정성을 위해 두 명령어 사이에 WAIT가 있어야 한다.
• 교착 상태
  • WRITE A TO B와 WRITE B TO A가 동시에 실행되면, 메모리 A와 메모리 B의 값이 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.

이 문제를 겪고 있는 학회원들이 지속적으로 SPC Team에 컨설팅 문의를 신청하고 있다. 반복되는 작업에 지친 SPC Team은 위와 같은 상황을 알아서 탐지하여 컨설팅해주는 프로그램을 만들고자 한다. 하지만 너무나도 바쁜 나머지, 유능한 프로그래머인 당신에게 프로그램의 제작을 의뢰했다. 너무나도 마음이 상냥한 당신은 이 의뢰를 거절할 수 없다!

입력

입력으로 최대 $10,000$ 줄의 명령어가 주어지며, WRITE문, READ문, EXIT문으로 구성된다. EXIT문은 마지막에 한 번만 주어진다.

각 명령어는 다음과 같이 정의되며, 메모리 이름은 $1$~$3$ 글자의 알파벳 대문자로 구성되어 있다.

• WRITE A TO B: 메모리 A의 내용을 메모리 B로 옮긴다. 이 때, 메모리 A는 READ 상태가 된다.
• READ A: 메모리 A의 데이터를 읽는다.
• EXIT: 프로그램을 종료한다.

WRITE A TO A 같이 동일한 메모리로 WRITE를 수행하는 경우는 없다.

출력

WAIT을 최소로 사용한 컨설팅 결과를 기존 명령어들의 순서를 유지하여 출력한다.

한 줄에 하나의 명령어만 출력해야 하며, 만약 그러한 컨설팅 결과가 여러 개라면 그 중 하나를 출력한다.

---

1. 문제를 해결하기 위해 사용한 것들

• Set과 Multimap을 이용하였다.
• Multimap을 이용하여 WRITE A TO B가 나타나면 Multimap에 A → B 와 B → A를 각각 저장해주었다.
• Set을 이용하여 READ A가 나타나면 Set에 A를 저장해주었다.
• 각각의 조건들(READ with WRITE / WRITE with WRITE / 교착상태 등)을 확인해주기 위해 Multimap의 메소드인 count를 중요하게 활용하였다. (count: 키가 매개변수로 지정된 키와 일치하는 multimap의 요소 수를 반환함)

2. 입력) string 클래스의 find와 substr 활용!

• 이 문제의 입력은 WRITE A TO B, READ A와 같이 명령어와 스페이스, 메모리의 이름으로 구분되어있다.
• 이를 getline으로 스페이스를 포함한 전체 명령어를 입력받는다.
• 따라서 string 클래스의 find 메소드를 통해 스페이스들의 인덱스를 알아내고 substr 메소드를 사용하여
  메모리의 이름을 쉽게 추출할 수 있다.
• 각 명령어들은 첫글자가 'W'인지, 'R'인지, 'E'인지 구분만 해주면 된다.

3. 알고리즘

• WRITE명령어가 들어오면 다음과 같이 처리한다.

  • 우선 WAIT가 필요한 상황인지 아닌지를 검사한다. WAIT가 필요하다면 WAIT를 결과 벡터에 넣고, 모든 multimap과 set을 비운 후, 선언한 multimap 두 개에 알맞는 pair들을 아래와 같이 넣는다. 그리고, 결과 벡터에 해당 명령 전체를 넣는다.

  • WRITE A TO B라고 했을 때, multimap<string, string> write_from_to에는 정순서 (A, B)를 넣어주고, multimap<string, string> write_to_from에는 역순서 (B, A)를 넣어준다.

    역순서를 넣는 이유는 WRITE with WRITE 의 첫 번째 조건처럼 WRITE A TO C가 먼저 들어오고 나중에 WRITE B TO C가 들어왔을 때, 이전에 C에 내용을 옮기려는 시도가 있었는지를 확인하기 위함이다. 이 경우, write_to_from.count(C)를 해서 나온 결과가 0이 아니라면 그러한 시도가 있었다는 것이 되고, WAIT를 결과 벡터에 넣어주면 되기 때문이다.

• READ명령어가 들어오면 다음과 같이 처리한다.

  • 우선 WAIT가 필요한 상황인지 아닌지를 검사한다. WAIT가 필요하다면 WAIT를 결과 벡터에 넣고, 모든 multimap과 set을 비운 후, set에 해당 메모리의 이름을 넣어준다. 또, 결과 벡터에 해당 명령 전체를 넣는다.
    (READ A라고 했을 때, set<string> read에 해당 메모리의 이름을 넣어준다(insert 메서드)).

• EXIT명령어가 들어오면 그냥 반복문 자체를 break 해버리면 된다.

#include <iostream> #include <string> #include <vector> #include <set> #include <map> using namespace std; multimap<string, string> write_from_to; multimap<string, string> write_to_from; multimap<string, string>::iterator it; set<string> read; vector<string> result; void clearAll() { write_from_to.clear(); write_to_from.clear(); read.clear(); } int main() { string command; while (true) { getline(cin, command); string a, b; int index1, index2, index3; if (command[0] == 'E') { result.push_back("EXIT"); break; } else if (command[0] == 'W') { index1 = command.find(" "); index2 = command.find(" ", index1 + 1); index3 = command.find(" ", index2 + 1); a = command.substr(index1 + 1, index2 - index1 - 1); b = command.substr(index3 + 1, command.length() - index3 - 1); // Read with Write 1 if (read.count(b) != 0) { result.push_back("WAIT"); clearAll(); } // Read with Write 2 + 교착상태 조건 else if (write_from_to.count(b) != 0 || write_to_from.count(a) != 0) { result.push_back("WAIT"); clearAll(); } // Write with Write else if (write_to_from.count(b) != 0) { result.push_back("WAIT"); clearAll(); } write_from_to.insert(make_pair(a, b)); write_to_from.insert(make_pair(b, a)); result.push_back(command); } else if (command[0] == 'R') { index1 = command.find(" "); a = command.substr(index1 + 1, command.length() - index1 - 1); // Read with Write if (write_to_from.count(a) != 0) { result.push_back("WAIT"); clearAll(); } read.insert(a); result.push_back(command); } } for (int i = 0; i < result.size(); i++) { cout << result[i] << "\n"; } }