[C++][백준] 아맞다우산(17244)

문제

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

"아 맞다 우산!!!"

경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

 

출력

S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

 

풀이

BFS와 DFS를 혼합하여 풀이하였습니다.

먼저 BFS를 통해 시작지점, 각 물건위치에서 다른 물건까지의 최단 경로를 구하여 dist 배열에 저장합니다.

 

다음으로 DFS를 통해 S에서 출발하여 모든 물건을 챙겨 E까지 도착할 수 있는 모든 경우의 수를 구합니다.

위 그림과 같이 다양한 경우의 수가 존재합니다.

각각의 경우에 대해 최소 시간을 갱신해주면 정답이 됩니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int answer = 987654321;
int N, M;

char map[55][55];
int map2[55][55];

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

int startX, startY, endX, endY;
int dist[7][7];

struct myData {
	int x;
	int y;
	int cnt;
};

vector<myData> items;
int item_num = 0;

int temp[5] = { 0, };
bool temp_check[5] = { false, };

bool isInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	else return false;
}

void bfs(int x, int y, int n) {
	bool visited[55][55] = { false, };
	queue<myData> myQueue;

	myQueue.push({ x, y, 0 });
	visited[x][y] = true;

	while (!myQueue.empty()) {
		int curX = myQueue.front().x;
		int curY = myQueue.front().y;
		int curC = myQueue.front().cnt;
		myQueue.pop();

		if (map[curX][curY] == 'X') { // 다른 물건인 경우
			int itemN = map2[curX][curY];
			dist[n][itemN] = curC;
		}
		else if (map[curX][curY] == 'E') { // 출구인 경우
			dist[n][item_num + 1] = curC;
		}

		for (int i = 0; i < 4; i++) {
			int nextX = curX + dirX[i];
			int nextY = curY + dirY[i];

			if (isInRange(nextX, nextY) && visited[nextX][nextY] == false && map[nextX][nextY] != '#') {
				visited[nextX][nextY] = true;
				myQueue.push({ nextX, nextY, curC + 1 });
			}
		}
	}

}

void find(char c) {
	int cnt = 1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == c) {
				if (c == 'X') {
					map2[i][j] = cnt++;
				}
				if (c == 'E') {
					
				}
				
				items.push_back({ i, j });
			}
		}
	}
}

void dfs(int x) {
	if (x >= item_num) {
		int totalDist = 0;

		totalDist += dist[0][temp[0]];
		for (int i = 0; i < item_num - 1; i++) {
			totalDist += dist[temp[i]][temp[i + 1]];
		}
		totalDist += dist[temp[item_num - 1]][item_num + 1];

		if (answer > totalDist) {
			answer = totalDist;
		}
	}
	else {
		for (int i = 1; i <= item_num; i++) {
			if (temp_check[i] == false) {
				temp_check[i] = true;
				temp[x] = i;
				dfs(x + 1);
				temp_check[i] = false;
			}
		}
	}
}

int main() {
	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> map[i];
	}

	find('S');
	find('X');
	find('E');

	item_num = items.size() - 2;

	for (int i = 0; i < items.size(); i++) {
		bfs(items[i].x, items[i].y, i);
	}

	for (int i = 0; i < 5; i++) {
		temp[i] = 0;
		temp_check[i] = false;
	}
	dfs(0);

	cout << answer;

	return 0;
}