문제 설명

• 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성
• 입력 : 정점의 개수 N, 그래프의 인접 행렬(0 : 없음, 1 : 있음) 단, i번째 줄의 i번째 숫자는 항상 0(자기 자신이니)
• 출력 : 정답을 인접 행렬 형식으로 출력

문제 해결 KEY_POINT

• 플로이드-워셜
• 그래프

문제 해결 아이디어

• 인접 행렬에 i에서 j로의 연결 여부를 표시 (방향 그래프임)
• 플로이드-워셜 알고리즘
  • i에서 k를 거쳐 j로 갈 수 있있으면 경로가 있다고 설정
• 경로 출력

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int vertex_num = 0;
    cin >> vertex_num;

    // 인접 행렬 초기화 (입력값은 0 또는 1)
    vector<vector<int>> matrix(vertex_num, vector<int>(vertex_num, 0));

    for (int i = 0; i < vertex_num; i++) {
        for (int j = 0; j < vertex_num; j++) {
            cin >> matrix[i][j]; // i에서 j로의 연결 여부 (방향 그래프)
        }
    }

    // 플로이드-워셜 알고리즘 적용
    // k: 중간 경유 정점, i: 시작 정점, j: 도착 정점
    for (int k = 0; k < vertex_num; k++) {
        for (int i = 0; i < vertex_num; i++) {
            for (int j = 0; j < vertex_num; j++) {
                // i에서 k를 거쳐 j로 갈 수 있으면 경로가 있다고 설정
                if (matrix[i][k] && matrix[k][j]) {
                    matrix[i][j] = 1;
                }
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < vertex_num; i++) {
        for (int j = 0; j < vertex_num; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

소감

플로이드-워셜에 대해 알고있다면 쉽게 풀 수 있는 문제였다. 보통은 가중치가 존재하는 문제가 많지만 이번 문제는 가중치를 신경쓰지 않고 경유지로 연결만 되어 있다면 연결되어있다고 하면 되는 문제였다.