백준 11403번 경로 찾기

문제 링크입니다: https://www.acmicpc.net/problem/11403

플로이드-와샬 알고리즘을 적용하여 푸는 문제였습니다.

여태까지 풀었던 플로이드 알고리즘 문제와는 달리 자기 자신한테도 가는 경우도 고려하는 것이 핵심이였습니다!

#include <iostream>

using namespace std;

 

const int MAX = 100;

 

int N;

int graph[MAX][MAX];

 

void floyd(void)

{

        //i->j로 가는 길이 없어도

        //k를 거쳐갈 수 있으면 갈 수 있다고 여긴다

        for (int k = 0; k < N; k++)

                 for (int i = 0; i < N; i++)

                         for (int j = 0; j < N; j++)

                                 if (graph[i][k] && graph[k][j])

                                          graph[i][j] = 1;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> graph[i][j];

 

        floyd();

 

        for (int i = 0; i < N; i++)

        {

                 for (int j = 0; j < N; j++)

                         cout << graph[i][j] << " ";

                 cout << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~