(C언어) 백준 알고리즘 문제 11403번 경로찾기

2022.08.25

푸는중..

floyd warshall로 푸는중..

DFS / BFS에 대해서 알아보기

#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가 아니라면 경로가 있다는 것이 된다.

#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");
}
}