백준 - 우주 탐사선 (C++)

Pixabay로부터 입수된 WikiImages님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/17182

17182번: 우주 탐사선

 

 이번 문제는 어떤 행성에서 다른 행성까지 가는 시간들이 주어졌을 때, 시작 행성에서 모든 행성을 다 탐사하는데 걸리는 최소 시간을 구하는 문제이다. 모든 행성을 최소 시간으로 탐사해야 하기에 행성에서 행성까지 최소 시간으로 움직여야 할 것이다. 그렇기에 이번 문제는 크게 두 단계로 나눌 수 있다. 

 

1. 행성 간 최단 시간 구하기

 우선, 각 행성에서 각 행성까지의 최소 이동 시간들을 구할 것이다. 이를 위해 플로이드 와샬 알고리즘을 이용할 것이다. 이 알고리즘은 간단히 말하자면 모든 지점에서 모든 지점까지의 최소 경로를 구할 수 있는 알고리즘이다. 자세한 설명은 최하단의 링크에서 확인할 수 있다.

 

int travelTime[MAX][MAX];

for (int mid = 0; mid < N; ++mid)
{
	for (int departure = 0; departure < N; ++departure)
	{
		for (int arrival = 0; arrival < N; ++arrival)
		{
			if (travelTime[departure][arrival] > travelTime[departure][mid] + travelTime[mid][arrival])
				travelTime[departure][arrival] = travelTime[departure][mid] + travelTime[mid][arrival];
		}
	}
}

여기서 travelTime은 입력으로 주어지는 행성 간의 이동 시간이다. 출발 행성과 도착 행성을 지정한 후, 모든 행성을 거쳐갈 때의 값을 비교한다. 만약 출발 행성에서 도착 행성까지 바로 가는 것(travelTime[departure][arrival])보다 중간 행성을 거쳐가는 것(travelTime[departure][mid] + travelTime[mid][arrival])이 더 빠르다면 값을 갱신한다.

 

2. 탐색

 

 이렇게 구해진 행성 간 최단 시간을 바탕으로 모든 행성을 탐색할 수 있는 최단 시간을 구해야 한다. 이는 재귀를 통해 구현할 수 있다. 현재 행성과 행성 탐색 기록을 바탕으로 모든 행성을 탐색했다면 답을 갱신하고 그렇지 않다면 방문하지 않은 행성을 탐색한다. 그런데 행성 탐색 기록을 어떻게 할 지가 문제이다. 단순히 전역 변수로 bool visited[11]; 같은 것을 이용하기가 힘들기 때문이다. 그렇기에 비트마스킹을 이용할 것이다.

 비트마스킹은 이진수로 자료를 표현하는 방법이다. 만약 주어진 행성이 총 3개(0번 행성 ~ 2번 행성)이고 하나도 방문하지 않았다면 000(2)으로 표현한다. 그리고 1번 행성을 방문했다면 010(2), 모든 행성을 방문했다면 111(2)로 표현할 것이다. 아래는 비트마스킹을 이용하기 위한 코드 일부분이다.

 

// &: and 연산자
bool Visited(int planet, int visitedRecord)
{
	if ((visitedRecord & (1 << planet))> 0)
		return true;
	else
		return false;
}

// visitAll: 모든 행성을 방문한 경우의 값
visitAll = (1 << N) - 1;

// 다음 행성을 방문한 경우의 기록
int nxtVisitRecord = visitRecord | (1 << nxtPlanet);

• a << b의 '<<'는 a를 b비트만큼 왼쪽으로 옮긴다는 뜻이다. 위의 코드의 '1 << planet'은 planet(행성 번호)만큼 1을 왼쪽으로 옮긴다는 뜻으로, planet이 0이라면 '1 << 0: 1(2)', '1 << 1: 10(2)', '1 << 2: 100(2)'가 될 것이다.
• &는 and 연산자이다. 이를 통해 두 비트에서 같은 부분이 있는지 검사할 수 있다. 위의 코드의 'visitRecord & (1 << planet)'을 보자. 만약 visitRecord가 '101(2)'(0번, 2번 행성 방문)이고 planet이 2라면 '1 << planet'은 '100(2)'가 되고 'visitRecord & (1 << planet)'는 0보다 큰 값이 된다.
• |는 or 연산자이다. 이를 통해 현재 기록에 다음 행성을 기록할 수 있다.

 

 이를 통한 모든 코드는 다음과 같다.

#include <iostream>
#define MAX 11
#define INF 987654321
using namespace std;

int answer = INF;
int visitAll;
int N, startingPlanet;
int travelTime[MAX][MAX];

bool Visited(int planet, int visitedRecord)
{
	if ((visitedRecord & (1 << planet))> 0)
		return true;
	else
		return false;
}

void Search(int planet, int searchTime, int visitRecord)
{
	if (visitRecord == visitAll)
	{
		if (answer > searchTime)
			answer = searchTime;
		return;
	}

	for (int nxtPlanet = 0; nxtPlanet < N; ++nxtPlanet)
	{
		if (Visited(nxtPlanet, visitRecord) == false)
		{
			int nxtVisitRecord = visitRecord | (1 << nxtPlanet);

			Search(nxtPlanet, searchTime + travelTime[planet][nxtPlanet], nxtVisitRecord);
		}
	}
}

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

	cin >> N >> startingPlanet;

	visitAll = (1 << N) - 1;

	for (int a = 0; a < N; ++a)
	{
		for (int b = 0; b < N; ++b)
			cin >> travelTime[a][b];
	}

	for (int mid = 0; mid < N; ++mid)
	{
		for (int departure = 0; departure < N; ++departure)
		{
			for (int arrival = 0; arrival < N; ++arrival)
			{
				if (travelTime[departure][arrival] > travelTime[departure][mid] + travelTime[mid][arrival])
					travelTime[departure][arrival] = travelTime[departure][mid] + travelTime[mid][arrival];
			}
		}
	}

	Search(startingPlanet, 0, (1 << startingPlanet));

	cout << answer << endl;

	return 0;
}

 

 

---

- 플로이드 와샬 알고리즘

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

- 플로이드 와샬 구현하기

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

- 비트마스킹

https://travelbeeee.tistory.com/451

[알고리즘] 비트마스킹(bitmasking) 이란