7-A dp초기화값 관련 시간초과 질문

안녕하세요 ㅎㅎ

좋은 의견입니다.

여기서 -1 : 방문하지 않은 정점을 의미하고 987654321은 방문을 했을 때의 초기값이라고 생각하시면 됩니다.

	dp[here][visited] = 987654321;
	//모든도시를 돌며, 방문안한곳으로 들어감!
	//i번째 도시로 갈 예정임.
	for (int i = 0; i < n; ++i) {
		//i번째 도시를 이미 방문했으면 탐색안함
		if (visited & (1 << i)) continue;
		if (w[here][i] == 0) continue; //갈수없는경우
		//i번째 도시 방문체크후, 그 비용을 더함
		dp[here][visited] = min(dp[here][visited], 
			dfs(i, visited | (1 << i)) + w[here][i]);
	}
	return dp[here][visited];

이러한 로직에서 for문이 작동이 안되면 dp 는 해당 초기값을 반환해야 하지만 + 방문했음 을 알려줘야 하거든요.

그렇기 때문에 서로 다르게 해야 합니다.

또한... -1이 아니고 다른 수로 해도 괜찮습니다.

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int n, w[16][16],dp[16][1<<16]; 
//[현재위치][방문한비트] : [방문비트]방문시 최소비용

int dfs(int here, int visited) {
	//모든지점을 방문한경우
	// ex ) 도시4개 : 1111
	// 10000(1<<4) 에서 -1 하면 1111이 된다!
	if (visited == (1 << n) - 1) {
		//다시 출발점(0번도시)로 갈수있으면 간다.
		if (w[here][0]) {
			return w[here][0];
		} //갈수없는 경로이면 배제시킴
		else return 987654321;
	}
	//계산된값이 있는경우 그거리턴
	if (dp[here][visited] != 1e9) return dp[here][visited];

	//초기값 = 최대로설정 (최소값 구하기니까)
	dp[here][visited] = 987654321;
	//모든도시를 돌며, 방문안한곳으로 들어감!
	//i번째 도시로 갈 예정임.
	for (int i = 0; i < n; ++i) {
		//i번째 도시를 이미 방문했으면 탐색안함
		if (visited & (1 << i)) continue;
		if (w[here][i] == 0) continue; //갈수없는경우
		//i번째 도시 방문체크후, 그 비용을 더함
		dp[here][visited] = min(dp[here][visited], 
			dfs(i, visited | (1 << i)) + w[here][i]);
	}
	return dp[here][visited];


}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> w[i][j];
		}
	}
	//memset(dp, -1, sizeof(dp));
	fill(&dp[0][0], &dp[0][0] + 16 * (1 << 16), 1e9);
	//[현재 : 0번도시] [0번도시 방문표시 비트키기]
	cout << dfs(0, 1);

	return 0;
}

이런식으로 문제 범위를 벗어나는 1e9로 해도 상관없습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

dbehdgns71님의 질문과 관련하여, “7-A 질문” 에 대한 지식공유자 큰돌님의 이미 답변된 내용이 도움이 될 것 같습니다. 해당 답변에서는 dp 배열의 초기화 값 설정과 관련된 오류와 문제의 조건을 충분히 고려하지 않은 부분을 지적하고 해결 방법을 제시합니다. 비록 정확히 같은 문제가 아닐 수도 있으나, dp 초기화와 관련하여 어떤 점을 주의해야 하는지에 대한 유용한 정보를 얻을 수 있습니다.

아래 링크에서 자세한 내용을 확인하실 수 있습니다:
- 7-A 질문에서 큰돌님은 dp를 초기화할 때의 주의점과 로직의 문제점을 설명하고 있습니다.

dp 배열을 -1로 초기화 한 후 계산된 값이 있으면 바로 return하는 방식과 fill로 987654321로 초기화한 뒤, 이를 바탕으로 로직을 구성할 때 차이점에 대해 다루고 있지는 않지만, dp 배열 초기화 및 조건 처리에 있어서 주의해야 할 점들에 대해서 배울 수 있으실 겁니다.

각 코드에서 dp 값을 초기화하는 방법의 차이가 시간 초과를 유발하는 다양한 요소들 중 하나일 수 있음을 염두에 두셔야 합니다. 최적화 문제에서 계산된 값의 재활용(logic reuse)을 위해서는 초기화 단계에서의 접근 방식이 성능에 큰 영향을 미칠 수 있습니다. 또한, dp 배열을 사용할 때의 전체적인 로직 구성 방법도 시간 복잡도에 영향을 줄 수 있으니 구현 세부 사항을 다시 검토해보시는 것도 좋을 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.