[BOJ] 백준 11403번 경로 찾기

문제 링크 및 문제 설명

[백준] 11403번 경로 찾기

지난번에 플로이드라는 문제를 통해서 플로이드-와샬 알고리즘을 공부해보았습니다. 이번 문제도 마찬가지로 플로이드-와샬 알고리즘을 사용하는 문제인데요. 단, 지난번 문제와 다르게 i행과 j행이 같은 경우도 따져주어야 합니다. 플로이드 문제가 궁금하신 분은 포스팅 하단 링크를 참고해주시기 바랍니다.

 

문제 소스 코드

#include <cstdio>

using namespace std;

int graph[102][102];
int n;
void floyd() {
	for (int k = 1; k <= n; k++) {
		//k : 거쳐가는 지점
		for (int i = 1; i <= n; i++) {
			// i : 출발지점
			for (int j = 1; j <= n; j++) {
				// j : 도착지점 
				if (graph[i][k] && graph[k][j]) {
					graph[i][j] = 1;
				}
			}
		}
	}
}


int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &graph[i][j]);
		}
	}

	floyd();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", graph[i][j]);
		}
		printf("\n");
	}

}

개발 환경 : Visual Studio 2019

 

참고하면 좋은 글

[백준] 11404번 플로이드