[백준/c++] 11403번: 경로 찾기

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

11403번: 경로 찾기

 

문제 요약

 

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서 i에서 j로 가는 경로가 있는지 없는지 구하라.

 

범위

 

정점의 개수 N (1 ≤ N ≤ 100)

i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다.

 

 

 

---

 

 

출력되는 형식을 보면 i번째 정점에서 다른 i-1개의 정점으로 가는 간선이 있는지 확인하기 위해 모든 정점에서 출발해야 한다. 그러므로 반복문을 통해 각 i 정점을 bfs 탐색을 한다.

 

graph 배열을 반복문을 통해 돌면서 만약 graph 배열 값이 0이거나 방문한 곳이라면 넘어가고 1이라면 큐에 넣어서 방문한다. i 정점과 연결된 모든 정점을 확인하고, 방문했다면(연결된 정점) 1 아니면 0으로 출력한다.

 

➿ 중요한 것은 방문을 확인하는 visited 배열을 false로 초기화해준다.

 

#include <iostream>
#include <queue>
using namespace std;
int n, graph[102][102];
bool visited[102];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> graph[i][j];
}

void bfs(int i){
    for(int k=1; k<=n; k++) visited[k] = false;
    queue<int> q;
    q.push(i);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int y=1; y<=n; y++){
            if(graph[x][y] == 0 || visited[y]) continue; //방문했거나 0이라면 넘어간다.
            visited[y] = true;
            q.push(y);
        }
    }
    for(int k=1; k<=n; k++) visited[k] ? cout << "1 " : cout << "0 ";
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    for(int i=1;i<=n;i++) bfs(i);
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!