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

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11403번: 경로 찾기

 

 

[문제 설명]

 

 

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

 

 

[입력]

 

 

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

 

 

[출력]

 

 

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

 

 

[입출력 예]

 

 

입력	출력
3 0 1 0 0 0 1 1 0 0	1 1 1 1 1 1 1 1 1
7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0	1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0

 

 

[문제 풀이]

 

 

문제를 또 제대로 안 읽고 풀다가 이상하다? 하고 다시 문제를 읽은 문제

 

가중치 없는 방향 그래프가 주어졌을 때 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구해야하는 문제이다.(처음에 문제 제대로 안읽어서 무방향 그래프인 줄 알았다.)

 

입력은 첫번째는 정점의 개수(N)가 주어지고, 

둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. 

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

0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

 

 

입출력 예1을 예시로 들어보도록 하겠다.

3
0 1 0
0 0 1
1 0 0

입력을 받았을 때 입력으로 주어진 인접 행렬을 인접 리스트로 변경했다.

vector<int> graph[101]; // 인접 리스트

for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            int n; cin >> n;
            if(n == 1) {
                // i 에서 j로 가는 간선이 존재한다.
                graph[i].emplace_back(j);
            }
        }
}

 

인접 리스트로 변경하게 되면 아래와 같은 인접 리스트와 인접 리스트 vector가 만들어진다.

 

 

이렇게 인접 리스트를 만들었으니

문제에서 구하고자 하는 내용을 다시 한번 살펴보자.

모든 정점에서 i에서 j로 가는 경로가 있으면 1, 없으면 0으로 출력해야한다.

 

우선 모든 정점을 탐색해야 하기 때문에 BFS를 이용하기로 했다.

그래서 모든 정점(1 ~ N)을 탐색 하기 위해 for문을 이용했다.

// 경로 탐색
for(int i = 1; i <= N; ++i) {
        // 각 정점을 확인한다.
        bfs(i);
}

 

우선 1번 정점부터 확인한다.

 

bfs(정점 번호)를 호출하면

void bfs(int cur) {
    int arr[101];
    bool visited[101];
    fill(arr, arr + 101, 0);
    fill(visited, visited + 101, false);

    queue<int> q;
    q.push(cur);
    while(!q.empty()) {
        int cur_vertex = q.front();
        q.pop();
        for(int element : graph[cur_vertex]) {
            if(visited[element]) continue;
            q.push(element);
            visited[element] = true;
            arr[element] = 1;
        }
    }
    for(int i = 1; i <= N; ++i) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
}

 

큐에 현재 정점(1)을 넣었다가 cur_vertex 변수에 현재 정점을 저장하고 뺀다.

 

 

그리고 현재 정점으로 부터 연결된 정점들을 확인한다.

1번 정점은 2번 정점이랑 연결되어 있고 2번 정점을 이전에 방문했는지 확인한다.

 

 

방문하지 않았다면 큐에 2번 정점을 넣는다.

그리고 2번 정점을 방문했다고 표시한다.

그리고 1번 정점은 2번 정점까지 갈 수 있기 때문에 경로 탐색 배열의 2번 정점(인덱스)에 1을 저장한다.

 

 

큐에서 2번 정점을 빼고 2번 정점과 연결된 정점을 확인한다.

2번과 연결된 정점은 3번 정점이고 이전에 방문했는지 확인한다.

이전에 방문하지 않았다면 큐에 3번 정점을 넣고, 3번 정점을 방문 표시한다.

3번 정점은 1번 정점에서 2번 정점을 통해 갈 수 있기 때문에 경로 탐색 배열의 3번 정점(인덱스)에 1을 저장한다.

 

큐에서 3번 정점을 빼고 3번 정점과 연결된 정점을 확인한다.

3번과 연결된 정점은 1번 정점이고 이전에 방문했는지 확인한다.

이전에 방문하지 않았다면 큐에 1번 정점을 넣고 정점을 방문 표시한다.

1번 정점은 2번정점과 3번정점을 통해 다시 자기 자신으로 되돌아 올 수 있으므로 경로 탐색 배열의 1번째 정점(인덱스)에 1을 저장한다.

다시 1번 정점을 빼고 1번 정점과 연결된 2번 정점을 확인한다. 2번 정점은 이전에 방문한 기록이 있기 때문에 넘어가고 BFS는 종료된다.

 

그리고 경로 탐색 배열을 정점의 개수의 범위만큼 for문을 이용하여 1번 정점이 갈 수 있는 경로를 출력한다.

 

나머지 정점 2번, 3번도 위와 같은 과정을 거치면 각 정점이 갈 수 있는 경로들을 알 수 있다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

int N;
vector<int> graph[101];

void bfs(int cur) {
    int arr[101];
    bool visited[101];
    fill(arr, arr + 101, 0);
    fill(visited, visited + 101, false);

    queue<int> q;
    q.push(cur);
    while(!q.empty()) {
        int cur_vertex = q.front();
        q.pop();
        for(int element : graph[cur_vertex]) {
            if(visited[element]) continue;
            q.push(element);
            visited[element] = true;
            arr[element] = 1;
        }
    }
    for(int i = 1; i <= N; ++i) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            int n; cin >> n;
            if(n == 1) {
                // i 에서 j로 가는 간선이 존재한다.
                graph[i].emplace_back(j);
            }
        }
    }
    
    // 경로 탐색
    for(int i = 1; i <= N; ++i) {
        // 각 정점을 확인한다.
        bfs(i);
    }
}