[BFS] BJ11403 경로 찾기

문제 출처: https://www.acmicpc.net/problem/11403

 

Solution

• 각 노드를 시작으로 BFS하면서 갈 수 있는 노드에 경로 표시한다.

Point

• 각 노드에서 BFS할 때 매번 visited 초기화
• 시작 노드로 돌아올 때 예외 처리하여 자기 자신에게 가는 길이 있는지 판별
• Directed 그래프이기 때문에 모든 노드를 시작으로 BFS 해볼 수 밖에 없다.

---

#include <iostream>
#include <queue>

using namespace std;

int N;
bool adjList[101][101] = { false };
bool path[101][101] = { false };
bool visited[101] = { false };

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> adjList[i][j];
        }
    }
}

void printInput() {
    cout << "N:" << N << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }
}

void output() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
}

void pathFindingBFS(int start) {
    queue<int> q;
    q.push(start);
    //visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        path[start][cur] = true;
        for (int i = 0; i < N; i++) {
            if (adjList[cur][i] && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    if (!visited[start]) // cycle 존재하지 않을 때, 즉 자신에게 돌아올 수 없을 때
        path[start][start] = false;
}

void pathFinding() {
    for (int i = 0; i < N; i++) {
        pathFindingBFS(i);
        for(int j = 0; j < N; j++)
            visited[j] = false;
    }
}

int main()
{
    input();
    //printInput();
    pathFinding();
    output();
}