역사

BFS문제 백준에서 BFS문제로 이제 남은것들은 자주 한번이상씩틀리는것같다.

뭐, 그게 중요한것은 아니니, 넘어가도록하자.

문제를 읽다보면, 인접리스트를 만드는게 편한것을 직감할수있고

역시, 배열의크기가 1000보다 작으므로, memset을쓰는데 부담은없었다.

 

DFS를 쓸지, BFS를 쓸지 결정하는부분은, 경로를 타고 끝까지 완전탐색했을때

해당하지 않는경우도 있다는 점에있다고 생각한다.

전체적인 탐색 이후 아무것도 해당하지않는 부분을 처리하는것은 상당히 까다로운일 이라 판단했고

이에 따라 BFS탐색으로 문제풀이 전략을세웠다.

 

#include<iostream>
#include<vector>
#include<cstring>
#include<utility>
#include<queue>
 
using namespace std;
 
int n, k, s;
vector<int> map[401];
vector<int> map2[401];
bool d1[401];
bool d2[401];
bool onn = false;
 
int bfs(int st, int ed) {
    queue<pair<int,int>> q;
    for (int i = 0; i < map[st].size(); i++) {
        if (d1[map[st][i]] == false) {
            q.push({ map[st][i], 1 });
            d1[map[st][i]] = true;
            if (d1[ed] == true) {
                return -1;
            }
        }
    }
    for (int i = 0; i < map2[st].size(); i++) {
        if (d2[map2[st][i]] == false) {
            q.push({ map2[st][i], 2 });
            d2[map2[st][i]] = true;
            if (d2[ed] == true) {
                return 1;
            }
        }
    }
    while (!q.empty()) {
        st = q.front().first; int dir = q.front().second;
        q.pop();
        if (dir == 1) {
            for (int i = 0; i < map[st].size(); i++) {
                if (d1[map[st][i]] == false) {
                    q.push({ map[st][i], 1 });
                    d1[map[st][i]] = true;
                    if (d1[ed] == true) {
                        return -1;
                    }
                }
            }
        }
        else if (dir == 2) {
            for (int i = 0; i < map2[st].size(); i++) {
                if (d2[map2[st][i]] == false) {
                    q.push({ map2[st][i], 2 });
                    d2[map2[st][i]] = true;
                    if (d2[ed] == true) {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        map[x].push_back(y);
        map2[y].push_back(x);
    }
    cin >> s;
    for (int i = 0; i < s; i++) {
        int x, y;
        cin >> x >> y;
        
        cout << bfs(x, y) << '\n';
        memset(d1, 0, sizeof(d1));
        memset(d2, 0, sizeof(d2));
    }
    return 0;
 
}

BFS를 하면서 특이사항은, 한방향으로 갔다가 (내려가는방향) 다른방향으로(거슬러 올라가는 방향)의 처리를 한BFS에서 처리를 계속하려고 했고, 가장 좋은방법은 인접리스트 2개, 그리고 방문여부 체크배열 2개를 사용해

한 BFS내에서 처리를하는방식으로 진행했다.

사실, 해당방식으로 진행하게되면 인풋의 크기가 조금만 더 커지게되도 Queue에서 메모리 초과가 날 확률이높지만

본 문제의 배열크기를보면 그닥 무리는없어보였다.