2098번: 외판원 순회

Memo

이번문제는 해결 방법에 필요한 방법인 비트마스킹을 모르고 있어서 해당 부분을 정리하느라 가장 시간이 오래 걸렸다. 비트마스킹을 사용하면 특정 노드를 방문처리해야하는 경우 쉽게 표현할 수 있다.

예를들어, {1, 2, 3, 4, 5} 라는 노드가 있다. 여기서 우리가 1번 부터 순서대로 5번노드까지 지나간다면 기존에는 아래와 같이 방문체크를 해주었다.

visited = {1}
visited = {1, 2}
visited = {1, 2, 3}
visited = {1, 2, 3, 4}
...

한 칸을 방문한 경우를 체크하는 경우 단일 배열로 가능하지만, 방문한 모든 노드를 체크해야한다면 우리는 엄청난 배열을 선언해야한다.

visited[1][1][1][1][1];
// 만약 1,3,5를 방문했으면
// visited[1][0][1][0][1] = 1;

하지만 2진수를 활용해 더욱 더 효율적으로 방문노드를 표현할 수 있다. 예를들어 1, 3, 5를 방문했으면 10101(2)로 표현할 수 있다. 즉, 5개의 노드의 모든 방문처리를 00000 ~̆̈ 11111(2) 으로 표현할 수 있는 것이다.

visited[11111(2)] = visited[63];

이제 여기까지는 알겠는데 도대체 저 visited[]안에 어떻게 2진수를 집어넣을 수 있는지 궁금했다. 생각보다 간단했다. 배열 인덱스를 참조하는 대괄호 안에 비트 연산을 사용해서 집어넣으면 되는 것이었다.

int main()
{
	int arr[8];

	arr[1 << 0] = 1;
	arr[1 << 1] = 2;
	std::cout << "arr[1] : " << arr[1] << std::endl;
	std::cout << "arr[2] : " << arr[2] << std::endl;
}

만약 우리가 1, 3, 5번 노드 방문처리를 하고 싶다면 아래와 같이 하면 된다.

int main()
{
	int dp[(1 << 5) - 1]; // dp[63]과 같은 의미이다!
	int visited = 0;
	
	visited = visited | (1 << 1);
	visited = visited | (1 << 3);
	visited = visited | (1 << 5);

	dp[visited] = val;
}