[백준 11403번] 경로 찾기 (C++)

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

---

경로 찾기 문제는 각각의 정점에 대해 BFS를 수행하여 해결할 수 있습니다. 단, 주대각선도 0이 될 수 있음을 주의해야합니다. 

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int linked[100][100];
int adj[100][100];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n; i++)  // 인접 행렬 입력 받음
        for(int j = 0; j < n; j++)
            cin >> linked[i][j];

    for(int i = 0; i < n; i++){
        int vis[100];
        fill(vis, vis + 100, 0);

        queue<int> q;
        q.push(i);

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

            for(int nx = 0; nx < n; nx++){
                if(linked[cur][nx] == 0 || vis[nx] != 0) continue; // 인접하지 않거나 이미 방문한 경우 방문하지 않음
                q.push(nx);
                vis[nx] = 1;
            }
        }

        for(int j = 0; j < n; j++) adj[i][j] = vis[j];  // 경로 행렬에 기록
    }
    
    for(int i = 0; i < n; i++){ // 경로 행렬 출력
        for(int j =0 ; j < n; j++)
            cout << adj[i][j] << " ";
        cout << "\n";
    }
}