JUNGOL/Intermediate_Coder/백트래킹-DFS/1681 : 해밀턴 순환회로

Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로

---

문제                                            

태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다.

오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다.

배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다.

 

그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 

어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면

알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다.

 

태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자.

 

입력 형식                                     

첫 줄은 배달해야 하는 장소의 수 N(1≤N≤12)이 주어진다. 이때, 출발지(회사)는 1번이다.

둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다.

비용은 양방향이 아니라 단방향으로 가기 위한 비용이다. 

 

예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며, 

2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 열에 주어진다. 

 

장소 사이에 이동할 수 있는 방법이 없다면 비용을 0으로 표시한다.

 

출력 형식                                     

회사에서 출발하여 오늘 배달해야 하는 모든 장소를 한 번씩 들러 물건을 배달하고 회사에 돌아오기 위한 최소의 비용을 출력한다.

 

입력 예                                        

5 
0 14 4 10 20 
14 0 7 8 7 
4 5 0 7 16 
11 7 9 0 2 
18 7 17 4 0

 

출력 예                                        

30

 

Hint!

예제의 비용 (경로)
10(1->4) 
+ 2(4->5) 
+ 7(5->2) 
+ 7(2->3) 
+ 4(3->1) 
= 30

---

HamiltonPath.h

#include <iostream>
#include <algorithm>

class HamiltonPath : public Base
{
private:
	int GetLeastCost(short arr[][12], int n, int locIdx = 0, int cost = 0, int depth = 0);
	void BlockPrevLocation(short arr[][12], int n, int locIdx);
	void BlockNextLocation(short arr[][12], int n, int locIdx);
};

 

HamiltonPath.cpp

void HamiltonPath::Code()
{
	int n;
	std::cin >> n;

	short arr[12][12]{};

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

	std::cout << GetLeastCost(arr, n);
}

/// <summary>
/// 최소 이동 비용을 반환한다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="locIdx">현재 지역 인덱스</param>
/// <param name="cost">누적 비용</param>
/// <param name="depth">깊이</param>
/// <returns>최소 이동 비용</returns>
int HamiltonPath::GetLeastCost(short arr[][12], int n, int locIdx, int cost, int depth)
{
	static int minCost{ 99999999 };

	if (depth == n)
	{
		return cost;
	}

	for (int i = 0; i < n; i++)
	{
		// 갈 방법이 없는 경우 패스
		if (arr[locIdx][i] == 0)
		{
			continue;
		}

		short curCost{ arr[locIdx][i] };
		if (cost + curCost > minCost)
		{
			continue;
		}

		short tempArr[12][12];
		for (int i = 0; i < n; i++)
		{
			std::copy_n(arr[i], n, tempArr[i]);
		}


		BlockPrevLocation(tempArr, n, locIdx);
		BlockNextLocation(tempArr, n, i);

		minCost = GetLeastCost(tempArr, n, i, cost + curCost, depth + 1);
	}

	return minCost;
}

/// <summary>
/// 이전 도시의 인덱스를 다른 도시에서 제거
/// </summary>
/// <param name="arr">배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="locIdx">이전 도시의 인덱스</param>
void HamiltonPath::BlockPrevLocation(short arr[][12], int n, int locIdx)
{
	for (int i = 0; i < n; i++)
	{
		arr[locIdx][i] = 0;
	}
}

/// <summary>
/// 다음 도시의 인덱스를 다른 도시에서 제거
/// </summary>
/// <param name="arr">배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="locIdx">다음 도시의 인덱스</param>
void HamiltonPath::BlockNextLocation(short arr[][12], int n, int locIdx)
{
	for (int i = 0; i < n; i++)
	{
		arr[i][locIdx] = 0;
	}
}

 

---

실행 결과 Success(100)

---

 

코드 해설

- 다른 도시를 중복해서 접근하지 못하도록 막기

다른 도시에서 진입하여 더 이상 해당 도시에 방문할 필요가 없을 때 중복해서 방문하여 루프에 빠지지 않도록 도시에 접근하는 방법을 모두 제거한다.

void HamiltonPath::BlockPrevLocation(short arr[][12], int n, int locIdx)
{
	for (int i = 0; i < n; i++)
	{
		arr[locIdx][i] = 0;
	}
}

void HamiltonPath::BlockNextLocation(short arr[][12], int n, int locIdx)
{
	for (int i = 0; i < n; i++)
	{
		arr[i][locIdx] = 0;
	}
}

 

- 시간 절약을 위한 중간 종료 처리

해당 경우를 끝까지 파악하지 않아도 기존의 경로가 더 빠른 경우 중간에서 더 이상 진행하지 않도록 막아야 한다.

		short curCost{ arr[locIdx][i] };
		if (cost + curCost > minCost)
		{
			continue;
		}

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로-JUNGOL