글 읽기 - 외판원순회 cache배열값 변경이 어떻게 되는지 질문드립니다

gofkdvjvl 4년 전 0

cache배열에 ans가 계산된 값을 따로 나중에 넣어주는 문장은 없는데 &로 참조를 해줘서 result가 변경된 값이 같은

메모리 주소를 참조하는 cache배열에도 변경된 값이 들어가게 되는 건가요??

제가 문법에 약해 질문드립니다

```

int &ans=cache[here][vis]; // ans를 참조를 이용해 접근

if(ans!=-1){

return ans;

}

```

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MAX 17	
const int INF=9876543210;//int 최대값보다 큰 수로 세팅(누가 시작했을까)

int w[MAX][MAX];
int cache[MAX][1<<MAX];
int n;

int tsp(int here,int vis){
	if(vis==(1<<n)-1){ //마지막 부분집합에 도달했을 때 (전집합)
		
		if(w[here][0]!=0){
			return w[here][0];
		}
		return INF; // 경로가 존재하지 않으면 최대값 반환하여 답에 반영되지 않게 한다
		
	}
	
	int &ans=cache[here][vis]; // ans를 참조를 이용해 접근
	if(ans!=-1){
		return ans;
	}
	ans=INF; // 최대값 초기화
	
	for(int next=0;next<n;next++){
		if(w[here][next]==0 || vis&(1<<next))continue; //경로가 없거나 이미 방문했다면 패스
		
		int temp=w[here][next]+tsp(next,vis|(1<<next));// 다른 분은 vis+() 하셨는데
// 실험적으로 | (추가연산)으로 추가 연산이 되나 보았는데 되었다
		if(ans>temp)ans=temp; // 최소값 치환
	}
	return ans; //반환하는 최종값
	
	
}

int main(void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	

	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>w[i][j];
		}
	}
	
	int ans=INF; // 초기화 (함수에서 &연산 참조로 접근가능)
	memset(cache,-1,sizeof(cache)); //-1로 초기화 
	
	cout<<tsp(0,1)<<'\n'; // 시작하는 정점, 방문한 정점(1)로 시작 
	

	
	
	return 0;
}

djm03178 4년 전 1

네. 그 문법에 대해 알아보세요. 참조자를 공부하시면 됩니다.

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

문제

문제

출처

ICPC

외판원순회 cache배열값 변경이 어떻게 되는지 질문드립니다

gofkdvjvl 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말