백준 11403 경로 찾기 (C++)

안유태·2022년 11월 18일
0

알고리즘

목록 보기
80/239

11403번: 경로 찾기

플로이드-워셜을 이용한 문제이다. 반복문을 돌면서 A[i][k]A[k][j]의 간선이 존재한다면 A[i][j]에 1을 저장해주고 출력해주었다.
플로이드-워셜 알고리즘을 풀어본 적이 있어서 간단하게 풀 수 있었다.



#include <iostream>

using namespace std;

int N;
int A[100][100];

void solution() {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (A[i][k] && A[k][j]) {
                    A[i][j] = 1;
                }
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글