UVA274 톰과 제리(C++)

톰과 제리는 방이 많은 집에 살고 있다.

수 많은 방 중에 톰과 제리는 각각 한개씩 자신만의 보금자리 방을 가지고 있다.

톰과 제리는 자신들의 보금자리로부터 출발하여 집을 돌아다닌다.

각각의 방에는 다른 방과 이어진 문이 있는데 모든 문들은 일방통행이며 톰과 제리가 사용할 수 있는 문들이 따로 있다.

예를 들어, A방에서 B방으로 통하는 톰 전용 문이 있으면 톰은 A에서 B로 이동 가능하지만 제리는 이동이 불가능하다. 또한 톰은 B에서 A로 돌아올려면 또 다른 문이 있어야만 한다.

집의 지도가 주어지면 다음을 구해야한다.

1. 톰과 제리가 만나는 곳의 존재유무
2. 톰을 만나지 않고 보금자리로부터 도달했다가 다시 보금자리로 돌아갈 수 있는 방의 존재 유무, 톰이 무슨짓을 하던간에 톰과 만나지 않아야 한다.

-입력 형식-

테스트 데이터의 개수//테스트 데이터 사이에도 빈줄이 입력된다.

(방의 개수) (톰의 보금자리 방) (제리의 보금자리 방)// 방의 갯수는 1~100까지
A방  B방//A방에서 B방으로 톰이 통과할수있는 문
     .
     .
     .
-1 -1 //톰이 지나갈수 있는 문의 입력 종료
A방  B방//A방에서 B방으로 제리가 통과할 수 있는 문
     .
     .
     .


-출력 형식-

(Y/N) (Y/N)//톰과 제리가 만나는 곳이 존재하는가? 톰을 만나지 않고 보금자리를 떠났다가 다시 돌아올 수 있는 방이 존재하는가?


#include <windows.h>
#include <sstream>
#include <string>
#include <deque>
#include <algorithm>
#include <memory.h>
using namespace std;
int main(){
    int rooms, toms, jerrys, cases, from, to, i;
    bool jerry[105][105], jerryreach[105];
    bool tom[105][105], tomreach[105];
    bool flag1, flag2;
    string str;
   
    deque<int> q;
   
    cin>>cases;
   
    while(cases-->0){
                     cin>>rooms>>toms>>jerrys;
                    
                     if(toms == jerrys){//제리와 톰의 보금자리가 같으면 불가피하게 만난다.
                             cout<<"Y N"<<endl;
                             continue;
                     }
                    
                     memset(tom, false, sizeof(tom));//배열을 모두 false로 초기화한다.
                     memset(jerry, false, sizeof(jerry));
                    
                    
                     while(1){
                              cin>>from>>to;
                              if(from<0)break;
                              tom[from][to]=true;//톰 전용 문들의 정보를 저장
                     }
                     cin.get();//end of the line 을 소비한다. 다음줄로 넘어간다.
                     while(1){
                              getline(cin,str);
                              if(str ==  "")break;//빈줄이 입력되면 순환문을 끝냄
                              istringstream os(str);
                              os >> from>> to;
                             
                              jerry[from][to] = true;//제리 전용문들의 정보를 저장
                     }
                    
                    
                     flag1 = flag2 = false;
                    
                     fill(tomreach,tomreach+105,false);//톰의 도달 정보를 초기화한다.
                     q.push_back(toms);
                    
                     tomreach[toms] = true;//톰의 보금자리는 도달이 가능하다.
                    
                     while(!q.empty()){/*덱의 앞부분에서 중복이 되지 않는 방문 가능한
                     모든 방들을 검색하고 더이상 검색가능한 방이 없을때 종료된다.*/
                                     for(i=1;i<=rooms;i++){
                                                           if(tomreach[i])continue;
                                                           if(tom[q.front()][i]){
                                                                                 q.push_back(i);
                                                                                 tomreach[i]=true;
                                                           }
                                                          
                                     }
                                     q.pop_front();
                     }
                    
                     if(tomreach[jerrys]){//톰이 제리의 보금자리에 도달할수 있으면
                                          cout<< "Y N" <<endl;
                                          continue;
                     }
                    
                     q.clear();
                    
                     fill(jerryreach, jerryreach+105, false);//제리가 도달할 수 있는 방 초기화
                    
                     q.push_back(jerrys);
                    
                     jerryreach[jerrys] = true;
                    
                     while(!q.empty()){
                                       if(jerry[q.front()][jerrys])flag2=true;
                                       //제리가 톰으로부터 안전한 경로로 다시 보금자리로 돌아옴
                                       for(i=1;i<=rooms;i++){
                                                             if(jerryreach[i])continue;
                                                             //이미 검색이 완료된 경로는 지나친다.
                                                             if(jerry[q.front()][i]){
                                                                                     jerryreach[i]=true;
                                                                                    
                                                                                     //톰이 가지 못하는 방으로만 검색
                                                                                     if(!tomreach[i]){
                                                                                                      q.push_back(i);
                                                                                     }else flag1 = true;
                                                             }
                                       }
                                      
                                       q.pop_front();
                                      
                                       if(flag1&&flag2)break;
                                       //결과를 얻으면 순환문을 당장 빠져나온다.
                     }
   
                     if(flag1)cout<<"Y ";
                     else cout<<"N ";
   
                     if(flag2)cout<<"Y";
                     else cout<<"N";
   
                     cout<<endl<<endl;
    }
   
    system("PAUSE");
    return 0;
}
                    
                                       
 실행결과

1

5 3 5
1 2
2 1
3 1
4 3
5 2
-1 -1
1 3
2 5
3 4
4 1
4 2
4 5
5 4

Y Y
Press any key to continue . . .