[C언어] BaekJun Algorithm Problem 1340
by RileyKim
(C언어) 백준 알고리즘 문제 11403번 경로찾기
2022.08.25
푸는중..
floyd warshall로 푸는중..
DFS / BFS에 대해서 알아보기
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define MAX 125 | |
#define INF 99999 | |
#define MIN(a, b) (a<b?a:b) | |
int mat[MAX][MAX]; | |
void floyd(); | |
int n; | |
int main(){ | |
scanf("%d", &n ); | |
floyd(); | |
} | |
void floyd(){ | |
//행렬 입력값 | |
for(int i = 0; i<n; i++ ){ | |
for(int j = 0; j<n; j++){ | |
scanf("%d", &mat[i][j]); | |
if(mat[i][j] ==0) | |
mat[i][j] = INF; | |
printf("mat[%d][%d] : %d \n",i, j, mat[i][j]); | |
} | |
} | |
for(int x = 0; x<n; x++){ | |
for(int i = 0; i<n; i++){ | |
for(int j = 0; j<n; j++){ | |
min(mat[i][x]) + mat[x][j], mat[i][j]); | |
} | |
} | |
} | |
} |
2022.08.29
floyd-warshall 해결 완료
하나 하나 정점을 잡아서 경로가 있으면 INF보다 작기 때문에 갱신된다.
최종적으로 INF이면 경로가 없다는 것이고 INF가 아니라면 경로가 있다는 것이 된다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define MAX 125 | |
#define INF 9999 | |
#define min(a,b) a<b?a:b | |
int mat[MAX][MAX]; | |
void floyd(); | |
int n; | |
int y; | |
int main(){ | |
scanf("%d", &n ); | |
floyd(); | |
} | |
void floyd(){ | |
//행렬 입력값 | |
for(int i = 0; i<n; i++ ){ | |
for(int j = 0; j<n; j++){ | |
scanf("%d", &mat[i][j]); | |
if(mat[i][j] ==0) | |
mat[i][j] = INF; | |
// printf("mat[%d][%d] : %d \n",i, j, mat[i][j]); | |
} | |
} | |
for(int x = 0; x<n; x++){ | |
for(int i = 0; i<n; i++){ | |
for(int j = 0; j<n; j++){ | |
mat[i][j] = min(mat[i][x]+mat[x][j], mat[i][j]); | |
// printf("%d ",mat[i][j]); | |
} | |
// printf("\n\n"); | |
} | |
} | |
// printf("-------------------------\n\n"); | |
for(int i = 0; i<n; i++){ | |
for(int j = 0; j<n; j++){ | |
if(mat[i][j] == INF){ | |
printf("0 "); | |
}else{ | |
printf("1 "); | |
} | |
// printf("%d ",mat[i][j]); | |
} | |
printf("\n"); | |
} | |
} |
Subscribe via RSS