글 읽기 - 왜 두 코딩은 서로 다른건가요?

ksoosung77 2년 전 0

오답코드는 왜 시간초과가 나는건가요?????? ;_;

아무리 봐도 모르겠네요 ㅠ

//정답 코드
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

vector<vector<int>>arr;
vector<bool>brr;

void DFS(int line, int p) {
	brr[p] = true;

	if (line == 4) {
		cout << 1;
		exit(0);
	}

	for (int i = 0; i < arr[p].size(); i++) {
		if(brr[arr[p][i]]==false)DFS(line + 1, arr[p][i]);
	}
	brr[p] = false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int f, n, a, b;
	cin >> f >> n;
	for (int i = 0; i < f; i++) {
		arr.push_back(vector<int>());
		brr.push_back(false);
	}
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	for (int i = 0; i < f; i++) {
		DFS(0, i);
	}
	cout << 0;
}

//오답코드(시간초과)
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

void DFS(vector<vector<int>>arr,vector<bool>brr,int line, int p) {
	brr[p] = true;

	if (line == 4) {
		cout << 1;
		exit(0);
	}

	for (int i = 0; i < arr[p].size(); i++) {
		if(brr[arr[p][i]]==false)DFS(arr, brr, line + 1, arr[p][i]);
	}
	brr[p] = false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int f, n, a, b;
	cin >> f >> n;
	vector<vector<int>>arr;
	vector<bool>brr;
	for (int i = 0; i < f; i++) {
		arr.push_back(vector<int>());
		brr.push_back(false);
	}
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	for (int i = 0; i < f; i++) {
		DFS(arr, brr, 0, i);
	}
	cout << 0;
}

floatingice 2년 전 1

오답코드 55번째 줄 void DFS를 보면, 함수가 호출되면서 매개변수인 arr와 brr이 그대로 전달되는 게 아니라, 같은 값을 가진 새로운 arr와 brr로 복사되어 전달됩니다.

매번 함수가 호출될 때마다 큰 N에 대해 복사가 일어나면서 오버헤드가 생기고 시간 초과가 되는 것 같네요.

arr와 brr이 복사되면서 낭비되는 시간을 줄이려면 윗 코드처럼 전역으로 두시거나, &arr로 참조형으로 쓰시면 됩니다.

참조형으로 쓰시면 값이 복사되는 대신 그대로 전달되어서 시간 낭비가 안 됩니다. 올려주신 코드에서 & 두 개만 달아서 전달하니 통과되네요.

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

문제

문제

출처

ICPC

왜 두 코딩은 서로 다른건가요?

ksoosung77 2년 전 0

floatingice 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말