[백준] 11403번 경로 찾기

문제: 11403번: 경로 찾기

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<vector<int>> graph(101, vector<int>(101));
vector<vector<int>> answer(101, vector<int>(101));

void BFS(int start) {
    vector<bool> visit(101, false); // 방문 배열을 매번 초기화
    queue<int> nexts;
    nexts.push(start);

    while (!nexts.empty()) {
        int cur = nexts.front();
        nexts.pop();

        for (int i = 0; i < n; i++) { // 0-based index 사용
            if (graph[cur][i] == 1 && !visit[i]) {
                visit[i] = true;
                answer[start][i] = 1; // start에서 i까지 도달 가능
                nexts.push(i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) { // 0-based index
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    // 모든 정점에서 BFS 실행
    for (int i = 0; i < n; i++) {
        BFS(i);
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << answer[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

기존 BFS 풀이에서 살짝 달라지는 점은 맨 처음 시작 노드를 nexts 에 넣을 때 방문처리를 바로 하지 않는 것이다.. ㄷㄷ 방문처리를 먼저 하고 while 돌리면 만약 시작 지점으로 돌아오는 길이 있을 때를 반영해주지 못해서 방문 처리를 하지 않는 것이었다.

 

이것만 생각해주면 나머지는 딱히 다를바가 없다. 외부에서 모든 정점을 시작지점으로 해서 BFS 를 돌려주면 된다. main 에서 BFS 돌리려고 할 때도 현재 시작 지점으로 주려고 하는 정점이 이미 방문한 곳인지 확인하지 않는다.