BFS, 가중치 있는 map

문제

주어지는 노드사이에는 최대 1개의 도로가 있으며 양방향 도로이다.

도로에는 가중치가 있으며 노드간 이동시에는 최단 경로로 이동한다.

N, 노드 수 : 5~100

M, 도로 수 : 5~5000

D, 노드 사이의 거리

 

이때 각 노드를 출발점으로 할때 도착 노드까지의 거리가 가장 먼 거리를 X라고 하자.

노드 중의 X가 가장 작은 X의 값을 구하라 

 

입력

N과 M이 입력되며

노드A와 노드 B 사이의 거리 D가 아래와 같이 입력된다.

5 7

1 2 5

3 2 14

2 4 5

1 3 10

4 3 15

5 4 15

3 5 8

 

출력

15

입력을 그래프로 표현하면 위와 같다.

---

접근방식

서로 다른 가중치가 있는 맵이므로 BFS로 접근이 유효하다.

BFS는 크게 2가지 종류가 있는데, 가중치가 서로 다른 경우와 가중치가 같은 경우가 그것이다.

- 가중치가 다를 경우 : 확산시 중복방문을 허용해야한다. 단 무조건 중복방문을 허용할 수는 없으며 visit배열에

방문 표시가 아닌 누적치를 저장한다. 또한 visit에 저장된 누적치보다 확산할 경로의 누적치가 더 이로울 경우에만 확산한다.

- 가중치가 같을 경우 : 가중치가 같다면 중복방문이 필요 없다.

 

1. 노드와 간선정보는 이차원배열로 표현할 수 있다. 입력정보를 이차원 배열로 표현한다.

2. 출발점으로 각 노드를 BFS로 탐색하며 각 출발점 마다의 X값을 구한다.

3. 단, 확산시 기존에 visit배열 보다 확산할 노드가 이로울 경우만 확산한다. (따라서 누적치 visit 배열을 특정 최대값으로 초기화할 필요가 있다.)

 

※ BFS 포멧

1) read point, write point, visit배열 등 초기화

2) 시작 노드 Enque

3) while(rp<wp) 동안 확산 + 확산 조건 및 Return 조건

 

 

원리

1) Enque시에 visit배열에 노드의 가중치 누적을 저장한다. (=이전 경로)

2) Deque하면서 기존 visit 배열에 저장된 누적치(=이전경로)보다 이로울 시 Data를 갱신한다.

 

 

#include <stdio.h>
#define MAX 100*100+10
int N; //공장수
int M; //도로수
int map[100+10][100+10];
int que[100*100*100];
int visit[100+10];
int A[5000];
int B[5000];
int D[5000];
int rp;
int wp;

void Input(){
	
	
	scanf("%d",&N);
	scanf("%d",&M);
	for(int i=1; i<=M; i++){
		//scanf("%d %d %d", &A[i], &B[i], &D[i]);
		scanf("%d", &A[i]);
		scanf("%d", &B[i]);
		scanf("%d", &D[i]);
	}
	
	MakeMap(A,B,D);
}

void MakeMap(int* A, int* B, int* D){
	//초기화
	for(int i=0; i<=N; i++){
		for(int j=0; j<=N; j++){
			if(i==j) map[i][j] =0;
			else map[i][j]=MAX;
			//map[i][j] =0;
		}
	}
	
	for(int i=1; i<=M; i++){
		map[A[i]][B[i]] = map[B[i]][A[i]]= D[i];
	}
	
}

void Enque(int node){
	que[wp++]=node;
}

int Deque(){
	return que[rp++];
}

int BFS(int sp){
	//초기화
	rp=0;
	wp=0;
	for(int i=1; i<=N; i++){
			visit[i] = MAX;
	}

	//시작점
	Enque(sp);
	visit[sp]=0;
	
	//확산
	while(rp<wp){
		int cur = Deque();
		for(int i=1; i<=N; i++){
			if(visit[i]> visit[cur]+map[cur][i]){
				visit[i]=visit[cur]+map[cur][i];
				Enque(i);//방문
			}
		}
		
	}
	
	int rtn=0;
	for(int i=1; i<=N; i++){
		if(rtn<visit[i])
			rtn = visit[i];
	}
	
	return rtn;
	
}

int main() {
	Input();
	//MakeMap();
	int ans = MAX;
	
	for(int i=1; i<=N; i++){
		int temp = BFS(i);	
		//printf("temp : %d\n",temp);
		if(ans>temp) ans = temp;
	}
	
	printf("%d\n", ans);
	
	/*
	printf("+++++++++++++++++\n");
	for(int j=1; j<=N; j++){
			printf("%d\t", visit[j]);
	}
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			printf("%d\t\t", map[i][j]);
		}
		printf("\n");
	}
	*/
	
	return 0;
}