글 읽기 - 하나는 정답 하나는 오답인데 차이를 잘 모르겠어요

goodjaeheui 4년 전 0

하나는 백터를 이용해서 했고

하나는 그냥 배열을 주고 했는데 어디서 틀린지 모르겠네요 ㅠㅠ

제가 봤을때는 두개 다 똑같아 보이는데

일반배열을 이용해서 dfs를 구현하여 푼건 맞고

벡터를 주고 푼게 자꾸 틀렸다고 나옵니다

밑에 소스코드 첨부하였습니다.

#include <iostream>
using namespace std;
#include <cstring>
#include <vector>
//-----------------------------백터 사용----------------------------//
/*
int w[15][15];

vector <int> v[15];
bool visit[15];
int first;
int n;
int min_n = 0;//맨 처음 초기화 된 min값
int countt = 0;

int MIN(int a, int b) {
	return a < b ? a : b;
}

void dfs(int num,int sum, int x ) {
	if (!visit[num]) {

		visit[num] = true;

		x++;

		for (int i = 0; i < v[i].size(); i++) {
			dfs(v[num][i], sum + w[num][v[num][i]], x);
		}
		visit[num] = false;//방문방문...방문 후 false처리
	}

	

	if (x == n&& first == num) {//돌아가는 것 포함
		min_n = (min_n == 0) ? sum : MIN(min_n, sum);
	}

}

int main() {
	memset(visit, false, sizeof(visit));
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> w[i][j];
			if (w[i][j] != 0) {
				v[i].push_back(j);// 각 정점들과 노드 연결
			}
		}
	}

	for (int i = 0; i < n; i++) {
		first = i;
		dfs(i, 0, 0);
		memset(visit, false, sizeof(visit));
	}
	cout << min_n << endl;
	return 0;
}*/

//------------------------------일반 배열----------------------------//
int n;
int arr[15][15];
int visit[15];
int min_n = 0;
int first;
int min(int a, int b) {
	return a<b ? a : b;
}

void dfs(int num, int sum, int x) {

	if (!visit[num]) {
		visit[num] = 1;
		x++;
		for (int i = 0; i < n; i++) {
			if (arr[num][i] != 0)
				dfs(i, sum + arr[num][i], x);
		}
		visit[num] = 0;
	}

	if (x == n && first == num) {
		min_n = (min_n == 0) ? sum : min(sum, min_n);
	}
}

int main() {

	cin >> n;
	memset(visit, 0, sizeof(visit));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		first = i;
		dfs(i, 0, 0);
		memset(visit, 0, sizeof(visit));
	}

	cout << min_n;
	return 0;
}
//------------------------------------------------------------------//

sait2000 4년 전 0

27번 줄 이상한데요 v[i]?

for (int i = 0; i < v[i].size(); i++) {

goodjaeheui 4년 전 0

저게 메인에서 보시다시피 벡터를 이용하여 정점과 정점끼리 이어져 있지 않은 것은 아예 벡터 안에 넣지 않아서

반복문을 돌릴때 for (int i = 0; i < v[i].size(); i++) 이런식으로 하게 되면 정점끼리 이어져 있지 않은 것은 생략할 수 있어서 좀더 시간을 단축시킬 수 있기때문에 이렇게 짰구요 실제로 둘다 실행은 똑같이 잘 됩니다..

계속 틀렸다고 나오는게 의문이네요 실행은 둘다 잘 되는데 ...

for (int i = 0; i < n; i++) {   //main()
		for (int j = 0; j < n; j++) {
			cin >> w[i][j];
			if (w[i][j] != 0) {
				v[i].push_back(j);// 각 정점들과 노드 연결
			}
		}
	}

sait2000 4년 전 1

v[num]이겠죠...

goodjaeheui 4년 전 0

그러게요........................... 감사합니다ㅠㅠ..............

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

문제

문제

출처

ICPC

하나는 정답 하나는 오답인데 차이를 잘 모르겠어요

goodjaeheui 4년 전 0

sait2000 4년 전 0

goodjaeheui 4년 전 0

sait2000 4년 전 1

goodjaeheui 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말