백준 - 17244번 아맞다우산 (C++)

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

17244번: 아맞다우산

 이 문제는 전형적은 너비 우선 탐색 문제라 생각한다. 시작 지점을 알아낸 후, 너비 우선 탐색을 통해 도착 지점에 도달한다. 그리고 그 때까지 걸린 시간을 반환한다. 하지만, 이 문제에서 신경써야 할 부분이 하나 있다. 그것은 문제의 경재씨가 외출하기 전에 꼭 챙겨야 하는 물건들이다. 즉, 단순한 최단 시간이 아닌, 모든 물건을 다 챙겼을 때의 최단 시간을 구하는 문제이다.

 챙겨야 하는 물건의 최대 개수는 5이다. 즉, 만약 5개의 물건이 존재한다면 가능한 경우의 수는 총 32가지이다.(1번 물건을 챙겼는지, 안 챙겼는지 2가지, 2번 물건에서 2가지, 마찬가지로 5번 물건까지 모두 2가지로 2 * 2 * 2 * 2 * 2 = 32) 그리고 이 모든 경우를 저장, 비교하하기 위해서는 비트마스킹이 적절할 것이다. 비트마스킹에 대한 개념은 쉽게 찾을 수 있으니 생략한다. 이 문제에서 필요한 비트마스킹 연산자는 다음과 같다.

• a | b: OR 연산자로, 현재 가지고 있는 물건에 다음 물건을 합칠 때 이용할 것이다.
• 1 << n: 1을 n 비트만큼 왼쪽으로 시프트 하는 것으로, n번 물건을 기록할 때 이용할 것이다.

그리고, 이것들을 이용해 작성한 코드는 다음과 같다.

1. 집의 열, 행의 길이를 입력 받는다.
2. 집의 구조를 입력 받는다.
   1. 만약 현재 위치에 물건이 있다면, 그 위치의 물건에 번호를 매긴다.
   2. 만약 현재 위치가 출발점이라면 따로 저장한다.
3. 모든 물건을 가지고 있을 대의 숫자를 저장한다. 각 물건의 비트는 (1 << 물건번호)로 알 수 있다. 그리고 물건을 합하는 것은 OR 연산을 통해 이뤄진다.
4. 너비 우선 탐색을 통해 답을 알아낸다.
5. 큐를 이용해 탐색을 한다.
   1. 만약 현재 위치가 도착 지점이면서 모든 물건을 가지고 있을 경우, 탐색을 그만하고 답(현재 시간)을 반환한다.
   2. 상, 하, 좌, 우 방향으로 탐색을 진행한다.
   3. 만약 다음 위치가 집 안이면서, 벽이 아니고, 현재 물건 상태로 방문한 적이 없다면 방문한다.
      1. 만약 다음 위치에 물건이 있으면, 그 물건을 가져간다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define MAX 51
#define ITEM 5

int R, C;									// 문제에서 주어지는 집의 행, 열 길이
int startR, startC;							// 시작 지점 (startR, startC)
int itemIdx = 0;							// 물건의 번호를 붙이고, 총 물건이 몇 개인지 저장하는 변수
int allItems = 0;							// 모든 물건을 소유했을 때의 경우
char home[MAX][MAX];						// 문제에서 주어진 집
bool visited[MAX][MAX][(1 << (ITEM + 1))];	// 각 경우에 따른 방문 기록
int nr[4] = { 1, -1, 0, 0 };				// 다음 칸의 방향 (행))
int nc[4] = { 0, 0, 1, -1 };				// 다음 칸의 방향 (열))

// 현재 위치 (r, c)가 주어진 집의 범위를 벗어나는지 검사하는 함수
// 만약 벗어나지 않는다면 true를 반환
bool IsIn(int r, int c)
{
	return 1 <= r && r <= R && 1 <= c && c <= C;
}

int Go()
{
	int answer = 0;

	// 5. 큐를 이용하여 탐색한다.
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push({ { startR, startC }, { 0, 0 } });
	visited[startR][startC][0] = true;

	while(!q.empty())
	{
		int curR = q.front().first.first;
		int curC = q.front().first.second;
		int curItems = q.front().second.first;
		int curTime = q.front().second.second;
		q.pop();	

		// 5-1. 만약 현재 위치가 도착 지점이면서 모든 물건을 가지고 있을 경우, 
		// 탐색을 그만하고 답(현재 시간)을 반환한다.
		if (home[curR][curC] == 'E' && curItems == allItems)
		{
			answer = curTime;
			break;
		}

		// 5-2. 상, 하, 좌, 우 방향으로 탐색을 진행한다.
		for (int i = 0; i < 4; ++i)
		{
			int nxtR = curR + nr[i];
			int nxtC = curC + nc[i];

			if (IsIn(nxtR, nxtC))
			{
				if (home[nxtR][nxtC] != '#' && visited[nxtR][nxtC][curItems] == false)
				{
					// 5-3. 만약 다음 위치가 집 안이면서, 벽이 아니고, 현재 물건일 때 방문한 적이 없으면
					// 방문한다.
					visited[nxtR][nxtC][curItems] = true;

					if ('0' <= home[nxtR][nxtC] && home[nxtR][nxtC] <= '9')
					{
						// 5-3-1. 만약 다음 위치에 아이템이 있으면,
						// 그 아이템을 가져간다.
						int nxtItem = home[nxtR][nxtC] - '0';
						int nxtItems = (curItems | (1 << nxtItem));

						q.push({ { nxtR, nxtC }, { nxtItems, curTime + 1} });
					}
					else
						q.push({ { nxtR, nxtC }, { curItems, curTime + 1 } });
				}
			}
		}
	}

	return answer;
}

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

	// 1. 집의 열, 행 길이를 입력 받는다.
	cin >> C >> R;


	// 2. 집의 구조를 입력 받는다.
	for (int r = 1; r <= R; ++r)
	{
		for (int c = 1; c <= C; ++c)
		{
			cin >> home[r][c];

			if (home[r][c] == 'X')
			{
				// 2-1. 만약 현재 위치에 물건이 있다면, 
				// 그 위치의 물건에 번호를 매겨준다.
				home[r][c] = (itemIdx + '0');
				++itemIdx;
			}
			else if (home[r][c] == 'S')
			{
				// 2-2. 만약 현재 위치가 출발점이라면
				// 따로 저장한다.
				startR = r;
				startC = c;
			}
		}	
	}

	// 3. 모든 물건을 가지고 있을 때의 숫자를 저장한다.
	for (int i = 0; i < itemIdx; ++i)
	{
		// 각 물건의 비트는 (1 << 물건번호)로 알 수 있으며
		// 이는 OR 연산을 통해 기록한다.
		allItems = (allItems | (1 << i));
	}

	// 4. 너비 우선 탐색을 통해 답을 알아낸다.
	int answer = Go();

	cout << answer << endl;
	
	return 0;
}