글 읽기 - 예시의 테스트케이스는 돌아가는데;; 시간초과가 나네요;

bsdlcksdn 8년 전 0

플로이드 와샬? 이라는 걸 처음접해봐서 잘 모릅니다;;;

다익스트라와 비슷한 느낌같아서 1238-파티 문제도 시간초과가 나더라구요;;(게시판에 글을 올렸으나 답이없네요;;)

제 생각대로 알고리즘 구현하여서 짜봤는데 시간초과가 나네요;

전자공학과 이다보니까 빅오 개념이나 시간복잡도를 잘 계산할줄 몰라요;;

어디서 시간초과가 가는건지 잘 모르겠습니다.

입력을 받고 n*n배열을 이중포문을 통해 재귀함수로 들어가게 되는데

그 밑에 이중포문 한 번 돌때마다 copy해놨던 배열을 다시 원본 배열에 입력시키는 과정에 의해 n*n*n*n이 됩니다.

혹시 이부분에서 시간초과가 나는걸까요??(n=100이라서 1억이라 시간초과가 안나지 않을까 햇는데요;;)

#include <iostream>
using namespace std;

int n, m;
int a, b, c;
int board[110][110];
int copy_board[110][110];
int new_board[110][110];
int max_count;
int check[110];
int temp;

void dijkstra(int data, int count, int start, int end) {
	//cout << data << " " << count << " " << start << " " << end << endl;

	if (data == end && max_count > count) {
		max_count = count;
		//cout <<"start : "<<start<<" end : "<<end<< " max : " << max_count << endl;
		new_board[start][end] = max_count;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cout << board[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;

		return;
	}

	else {

		for (int j = 1; j <= n; j++) {

			if (board[data][j] != 0 && max_count > count + board[data][j] && check[j] == 0) {
				check[j] = 1;

				temp = board[data][j];
				board[data][j] = 0;

				dijkstra(j, count + temp, start, end);

				board[data][j] = temp;

				check[j] = 0;
			}
		}
	}
}


int main() {

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		if (board[a][b] == 0)
			board[a][b] = copy_board[a][b] = c;
		else if (board[a][b]>c) {
			board[a][b] = copy_board[a][b] = c;
		}
	}

	//검사
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << copy_board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/


	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			max_count = 99999999;

			if (i == j) {
				new_board[i][j] = 0;
				continue;
			}
			check[i] = 1;
			dijkstra(i, 0, i, j);

			//복사(초기화)
			for (int i = 1; i <= n; i++) {
				check[i] = 0;
				
			}


		}
	}



	//출력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << new_board[i][j] << " ";
		}
		cout << endl;
	}
}

o(n^4) 으로 짜셨다면, 시간초과가 날것 같습니다ㅜ

말씀하신 전쌍에 대한 최단경로를 구하는 플로이드워셜 알고리즘의 경우에는 시간복잡도가 O(n^3)입니다.
https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%E...
를 참고하시면 도움이 되실것 같습니다.!

다익스트라로 구현 하시는경우에도, 하나의 start 지점에서 나머지 노드들에 대해의 최단거리를 구하는데에 O(n^2) 혹은 자료구조에 따라 (nlog(n)) 이 소요됩니다.
따라서 다익스트라를 n번 돌리시면, o(n^3) 혹은 o(n^2 log(n)의 시간복잡도로 이문제를 해결하실수 있을것으로 보입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예시의 테스트케이스는 돌아가는데;; 시간초과가 나네요;

bsdlcksdn 8년 전 0

HJY 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말