UVA274 Cat and Mouse

BFS, Graph

출처: UVA UVA274 Cat and Mouse

SOL)
BFS탐색법으로 갈수 있는 곳을 각각 체크 후 만나는지 안만나는지 검사
그 후 고양이가 갈 수 있는 경로를 제외하여 쥐가 다시 돌아올 수 있는지 검사
쉬운데 입,출력 때문에 오래결림



[-] Collapse

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

bool meet, comeback;
int testCase;
bool cat[101], mouse[101];
int mouseHome, catHome;
int roomNum;
vector<int> catGraph[101], mouseGraph[101];
queue<int> q;

void init(){
    for (int i = 0; i < 101; i++) {
        catGraph[i].clear();
        mouseGraph[i].clear();
        cat[i] = mouse[i] = false;
        meet = comeback = false;
    }
}

void BFS(vector<int> *ptr, bool *visit){
    while (!q.empty()){
        int here = q.front();
        visit[here] = true;
        q.pop();
        for (int i = 0; i < ptr[here].size(); i++){
            int next = ptr[here][i];
            if (!visit[next])
                q.push(next);
        }
    }

}
void CanReturn(){
    for (int i = 0; i < 101; i++)
        mouse[i] = false;
    q.push(mouseHome);
    int cost = 0;
    while (!q.empty()){
        int here = q.front();
        if(cost != 0)
            mouse[here] = true;
        q.pop();
        cost++;
        for (int i = 0; i < mouseGraph[here].size(); i++){
            int next = mouseGraph[here][i];
            if (!mouse[next] && cat[next] != true)
                q.push(next);
        }
    }
    if (mouse[mouseHome])
        comeback = true;
    else
        comeback = false;
}

int main(){
    cin >> testCase;
    int cost = 0;
    while (testCase--){
        if (cost != 0) cout << endl;
        cost++;
        init();
        cin >> roomNum >> catHome >> mouseHome;
        int from = 0, to = 0;
        while (cin >> from >> to){
            if (from == -1 && to == -1) break;
            if (from != to)
                catGraph[from].push_back(to);
        }
        cin.get();
        string str, tempStr;
        while (1){
            getline(cin, str);
            if (str == "" || tempStr == str) break;
            tempStr = str;
            istringstream os(str);
            os >> from >> to;
            if (from != to)
            mouseGraph[from].push_back(to);
        }
        q.push(catHome);
        BFS(catGraph, cat);
        q.push(mouseHome);
        BFS(mouseGraph, mouse);
        for (int i = 0; i < 101; i++){
            if (cat[i] == true && mouse[i] == true)
                meet = true;
        }

        CanReturn();

        if (meet == true && comeback == true) cout << "Y Y" << endl;
        else if (meet == true && comeback == false) cout << "Y N" << endl;
        else if (meet == false && comeback == true) cout << "N Y" << endl;
        else cout << "N N" << endl;
    }
    return 0;
}