7-A 2분대 설명에 대해 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-A

해결된 질문

2025. 03. 16. 15:51 작성

안녕하세요,

2분대에서,

a->b->c 든, a->c->b 든 순서는 상관 없이 둘 중 최적을 구하고 d로 간다고 말씀하신걸로 이해했습니다.

그런데, a->b->c 인지, a->c->b인지 실제로 중요하고, 둘 다 탐색 해야하는 것 아닌가요..?

a->b->c 인 경우와 a->c->b인 경우 모두 tsp() 함수 호출 시점에 argument로 전달되는 visited 값은 같겠지만, here 값이 달라지는데..

오히려 반대로, 코드의 흐름상 결과적으로 일어나는 일은:

tsp(c, {a, b, c}) 에서 tsp(d, {a, b, c, d}) + dist[c][d]
tsp(b, {a, c, b}) 에서 tsp(d, {a, b, c, d}) + dist[b][d]

위 1번과 2번 사이의 비교 아닌가요..?

이 경우 분명히 순서가 중요한 것 같아서 헷갈립니다! ㅎㅎ

좋은 강의 항상 잘 듣고 있습니다.

감사합니다 🙂

c++코딩-테스트

답변 2

큰돌

지식공유자

2025. 03. 16. 23:51

안녕하세요 성혁님 ㅎㅎ

이 경우 분명히 순서가 중요한 것 같아서 헷갈립니다! ㅎㅎ

-> 순서가 중요합니다. ㅎㅎ 맞는 말씀입니다.
다만 제가 2분대의 저기서 순서가 상관없다라는 의미는 순서에 대한 상태값을 코드에 넣어도 되지 않는 것(배열에다가 해당 상태값을 고려할 필요x) 을 의미합니다.

TSP의 비트마스킹 DP에서 중요한 점은 방문 집합(visited) 자체는 방문한 정점들의 집합일 뿐, 순서를 기록하지 않는다는 것이니까요. ㅎㅎ

다만 성혁님 말씀대로 a, b, c를 방문한 경우 visited는 둘 다 같은 값(예, {a, b, c})이지만, 현재 위치(here) 가 다르면 다음 단계로 이동하는 비용이 달라지는것은 맞습니다. 이부분은 코드 내에서 판단하고 있고 저 비용들이 최종적으로는 방문집합의 min으로 되게 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

2025. 03. 16. 15:56

안녕하세요, 인프런 AI 인턴입니다. 최성혁님은 Traveling Salesman Problem(TSP) 관련된 질문을 주셨으며, 특히 순열의 순서가 어떻게 중요하지 않을 수 있는지에 대해 의문을 가지고 계신 것으로 보입니다.

이해해야 할 핵심:

비순서적 상태 인식: TSP 문제는 모든 정점을 한번씩 방문하는 최소 경로를 찾는 것이 목표입니다. 여기서 중요한 것은 도달해야 하는 ‘상태’이지 ‘순서’가 아닙니다. 즉, {a, b, c}의 상태에 도달하는 여러 순서가 있을 수 있으나, 하나의 상태로 취급합니다.
비트마스크를 통한 방문 기록: visited 비트마스크는 정점들이 방문되었는지를 기록합니다. {a->b->c}와 {a->c->b}는 도달 상태로는 동일한 {a, b, c}를 의미하지만, 실제 탐색 경로에서는 여전히 결과가 달라질 수 있습니다. 마찬가지로 here에 대한 처리를 통해 다른 경로가 처리됩니다.
재사용 및 최소값 저장: 메모이제이션 기법을 통해 이미 최적값이 저장된 상태(visited)에 대해서는 추가 탐색을 피하고 저장된 최소값을 반환합니다. 이는 중복 계산을 피하는 핵심 전략입니다.

상세 설명:

tsp(here, visited)에서 visited의 상태가 이미 최적값으로 계산된 적이 있다면, 그 값을 그대로 재사용합니다.
모든 방문 상태에 대해 최적의 경로를 계산하고 저장합니다.
두 경로(a->b->c와 a->c->b)는 상태 인식에서는 동일하지만, 탐색 과정 중 경로 비용이 달라질 수 있어 최솟값 비교가 의미를 갖게 됩니다.

인프런 커뮤니티 질문&답변