[이코테] 실전 문제

최단 경로 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 이를 각각 구현하는 포스트는 다음에 올리겠다.

 

한 지점에서 특정 지점까지의 최단 경로를 구할 때에는 다익스트라를, 모든 지점에서 모든 지점까지의 최단 경로를 구할 때는 플로이드 워셜을, 다익스트라와 같은 경우지만 음의 가중치를 가진 간선이 존재할 경우 벨만 포드 알고리즘을 사용하면 된다.

 

미래 도시

방향이 없고 가중치가 없는 그래프로 1번 회사에서 K번 회사로, K번 회사에서 X번 회사로 가는 최단 경로를 구하는 문제였다. 나는 이 문제를 1번부터 K번, K번부터 X번까지의 최단 경로를 다익스트라를 이용해 구한 후 두 개의 값을 더해서 풀었는데 책에서는 전형적인 플로이드 워셜 유형의 문제라고 했다. 노드와 간선의 개수가 100개까지라고 제한되어 있어서 이때 100*100*100 = 1000000 밖에 되지 않아 간단하게 구현할 수 있는 플로이드 워셜 방법으로 푸는 것이 효과적이라고 했다. 하지만 다익스트라 방법이 플로이드 워셜 방법보다 풀이 과정은 복잡하지만 결관느 더 효율적이라고 생각했기 때문에 내가 푼 방법을 고치지는 않았다.

 

풀이 방법은 주석으로 상세히 달아놔서 따로 적진 않는다.

#define MAX_INT 101

int N, M, X, K; //회사 개수, 경로 개수, 목적지1, 목적지2 (1~X + X~K 찾는 문제)
int g[102][102] = { 0 };
int dist[102];


int findMin(int start, int dest) {
	priority_queue<pair<int, int>> pq; //dist, node 저장
	int nowNode, nowDist;
	int i;

	fill(dist, dist + N + 1, MAX_INT); //모든 dist를 MAX로 초기화

	pq.push(make_pair(0, start)); //시작점 넣기, 시작점은 dist가 0
	dist[start] = 0;

	while (!pq.empty()) {

		nowNode = pq.top().second;
		nowDist = pq.top().first; //지금까지 걸린 비용
		
		pq.pop();
		if (nowNode == dest) return dist[dest]; //현재 노드가 목적지 노드면 바로 리턴
		if (nowDist > dist[nowNode]) continue; //지금까지 걸린 비용 > start에서 nowNode로 바로 가는 비용 -> 이미 끝난 node라서 무시

		for (i = 1; i <= N; i++) {			
			if (g[nowNode][i] == 1) {
				int cost = nowDist + 1; //nowNode를 거쳐서 가는 비용
				if (cost < dist[i]) { //nowNode를 거쳐서 가는 비용 < start에서 i(nextNode)로 바로 가는 비용 -> nowNode를 거쳐서 가는 것으로 비용 업데이트 해야함
					dist[i] = cost;
					pq.push(make_pair(dist[i], i));
				}
			}			
		}
	}
	return MAX_INT;
}

int main() {
	int i, j;
	int a, b;

	scanf("%d %d", &N, &M);
	for (i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		g[a][b] = 1;
		g[b][a] = 1;
		dist[i + 1] = 101; //최댓값으로 초기화
	}
	scanf("%d %d", &X, &K);

	priority_queue<pair<int, int>> pq; //dist, node 저장

	pq.push(make_pair(0, 1)); //1 넣기 
	dist[1] = 0;

	int firstMin, secondMin;

	firstMin = findMin(1, K);

	if (X < K)	secondMin = findMin(X, K);
	else secondMin = findMin(K, X);

	if (firstMin == MAX_INT || secondMin == MAX_INT) printf("-1");
	else printf("%d", firstMin + secondMin);

}

/*
5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

4 2
1 3
2 4
3 4
*/

 

---

전보

방향이 있고 가중치가 있는 그래프로 시작 지점(C)과 연결된 모든 node들까지의 최단 경로(최소 시간)를 구해야 하는 문제였다.  위의 문제를 다익스트라로 풀어서 풀이 과정은 거의 동일했다. 단지 위의 문제는 목적지가 있다는 것이고 이번 문제는 특별한 목적지 없이 연결된 모든 정점까지의 최단 경로를 구해야 한다는 점이 달랐다.

 

먼저 다익스트라 알고리즘을 통해 dist[] (시작점부터 n까지의 최소 시간)을 구하고 dist의 값이 MAX가 아닌 도시의 개수(cnt)와 dist 값들 중 가장 큰 값(총 걸리는 시간)을 구해서 해결했다.

 

위의 문제와 마찬가지로 자세한 풀이 과정은 주석으로 달았다

#define MAX_INT 2000000000

int N, M, C;
vector<pair<int, int>> g[30001]; //연결된 node의 node 번호와 걸리는 time
int dist[30002]; //C부터 n까지 도달하는 데 걸리는 시간 -> MAX로 초기화 해줘야 함

void dijk(int start) {//각 n까지의 최소 시간을 다익스트라를 통해 저장
	priority_queue<pair<int, int>> pq; //time, node -> time을 기준으로 정렬돼야 해서	
	int nowNode, nowTime;
	int i;

	pq.push(make_pair(0, start));
	dist[start] = 0; //시작점에서 시작점까지 걸리는 시간은 0

	while (!pq.empty()) {
		nowNode = pq.top().second; //현재 노드
		nowTime = pq.top().first; //지금까지 걸린 시간
		pq.pop();

		//printf("nowNode: %d nowTime: %d nowDist: %d\n", nowNode, nowTime, dist[nowNode]);
		if (nowTime > dist[nowNode]) continue; //이미 보장된 노드 //이 조건이 없다면 양방향일 경우 영원히 탐색함

		for (i = 0; i < g[nowNode].size(); i++) { //연결된 모든 노드 탐색
			int nextNode = g[nowNode][i].first;
			int cost = g[nowNode][i].second + nowTime; //다음 노드까지 걸리는 시간은 nowNode에서 다음 노드까지 걸리는 시간 + nowNode까지 걸린 시간
			if (cost < dist[nextNode]) {//nowNode를 거쳐서 nextNode로 가는 시간 < C에서 바로 nextNode로 가는 시간 인 경우 dist값 수정
				dist[nextNode] = cost; 
				pq.push(make_pair(dist[nextNode], nextNode));
			}
			//printf("nowNode: %d nextNode: %d cost: %d dist[nextNode]: %d\n", nowNode, nextNode, cost, dist[nextNode]);

		}
	}

} 

int main() {
	int X, Y, Z;
	int i;
	int cnt = 0, time=0;

	scanf("%d %d %d", &N, &M, &C); //도시 개수, 통로 개수, 시작점

	for (i = 0; i < M; i++) {
		scanf("%d %d %d", &X, &Y, &Z);
		g[X].push_back(make_pair(Y, Z));
	}
	
	fill(dist, dist + N+1, MAX_INT);

	dijk(C);

	for (i = 1; i <= N; i++) {
		if (dist[i] != MAX_INT) {
			cnt++;
			if (dist[i] > time) {
				time = dist[i];
			}
		}
	}

	printf("%d %d", cnt-1, time); //start는 제외하고 세야 함
}

/*
3 2 1 
1 2 4 
1 3 2
*/

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24