글 읽기 - 10971 외판원순회2 문제 질문

wlckd90 6년 전 0

이 코드에서 제가 의문이 드는게

만약 순열을 뜻하는 벡터d에

0 1 2 3이 들어있고 그럼

0 1 체크

1 2 체크

2 3 체크 할텐데 만약에

2에서 3 갈수있고 그럼 ok = true이고, 3에서 0 도 갈수있고, 그럼 32번 째 줄

if (ok && a[d[n - 1]][d[0]] != 0)이 참일테니까 sum에 a[3][0]이 들어가겠지요?

근데 이 케이스는 2->3 , 3->0으로 갈수있지만 0->1, 1->2는 못갈때도 계산해버려서 논리적으로 맞지 않은 코드 아닌가요?

제가 어느 부분을 간과하고 있는지 잘 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector < vector<int> > a(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	vector<int> d(n);
	for (int i = 0; i < n; i++) {
		d[i] = i;
	}
	int ans = 2147483647;

	do {
		bool ok = true;
		int sum = 0;
		for (int i = 0; i < n - 1; i++) {
			if (a[d[i]][d[i + 1]] == 0) {	
				ok = false;
			}
			else {
				sum += a[d[i]][d[i + 1]];
			}
		}
		if (ok && a[d[n - 1]][d[0]] != 0) {
			sum += a[d[n - 1]][d[0]];
			if (ans > sum) ans = sum;
		}
	} while (next_permutation(d.begin(), d.end()));

	cout << ans << '\n';
	return 0;
}

aimpugn 6년 전 0

0 -> 1, 1 -> 는 못갈 때도 계산한다는 게 무슨 말이죠?

0 -> 1

1 -> 2

2 -> 3

3 -> 0이 되는 거 아닌가요?

wlckd90 6년 전 0

그러니까 만약에

조건이

2->3
3->0
이렇게 2가지만 가능할때가 있다고 하면 do while문을 수행하고 나면(비용이 1이라고할때) sum이 2가 되지 않나요??

왜냐하면 원래 0->1 1->2에서 체크하고 못가면 종료해야할텐데 저 코드에는 종료하는게 없어서 안되야 하는게 아닌가요...

aimpugn 6년 전 1

만약 0->1, 1->2는 못갈 경우에는

25번 줄에서 걸러지겠죠?

if (a[d[i]][d[i + 1]] == 0) {
ok = false;
}

문제에서 갈 수 없다면 0이라고 했으므로, 0->1과 1->2로 못 가는 경우라면 ok = false가 되고

다시 원점으로 돌아가는 부분이 sum에 추가가 안되고 sum이 ans에도 들어가지 못할 거 같습니다.

그렇다면 굳이 종료하는 부분이 없더라도 알아서 계산이 안되겠죠?

wlckd90 6년 전 0

아 이미 ok = false로 해서 값을 바꿨네요.

제 질문을 다시봐도 제가 한심해 보이네요 답변 감사합니다 이해했어요.

그니까 하나라도 i에서 i+1번째꺼로 가는게 0이면 ok = false로 되버리니까 밑에꺼 진행이 안된다는 거군요

for문 끝날때 ok=true가 되서 진행된다는 이상한 생각을 했어요. 감사합니다!!

aimpugn 6년 전 1

본인 오류는 잡아내기가 어렵더라구요. 저도 헷갈린 김에 다시 보니 복습이 됐네요. 도움이 됐다니 다행입니다. 많이 푸세요~

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

문제

문제

출처

ICPC

10971 외판원순회2 문제 질문

wlckd90 6년 전 0

aimpugn 6년 전 0

wlckd90 6년 전 0

aimpugn 6년 전 1

wlckd90 6년 전 0

aimpugn 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말