Search
Duplicate
🙆🏻‍♀️

경로 찾기

주차
18
문제번호
11403
언어
티어
실버
유형
플로이드-와샬
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

메모리

시간

1116 KB
0 ms

문제 풀이

그래프의 인접행렬이 주어지고 노드끼리 연결이 되어 있는지 0과 1로 출력하는 문제이다.
연결되어 있다면 1로 출력을 하고 아니라면 0으로 인접행렬 형식으로 출력한다.
연결되어 있다는 것은 x,y와 y,z 이 1이라면 x,z도 연결되어 있다는 의미로 3중 for문으로 탐색하였다.
start, end, mid 변수로 start - mid 와 mid - end가 연결되면 start - end 도 1로 저장하였고
모든 좌표를 탐색한 뒤 저장한 배열을 출력하면 경로연결 여부를 알 수 있게 된다.

Code

#include <cstdio> using namespace std; int main() { int arr[100][100]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]); } for (int mid = 0; mid < n; mid++) for (int start = 0; start < n; start++) for (int end = 0; end < n; end++) if (arr[start][mid] && arr[mid][end]) arr[start][end] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%d ", arr[i][j]); printf("\n"); } return 0; }
C++
복사