[C++] 백준 18188번: 다오의 데이트

문제 링크

18188번: 다오의 데이트

문제 요약

다오가 디지니를 만나러 가는데, 마리드가 방해를 한다. 마리드의 방해에 의해 다오는 총 N번 움직일 수 있으며, 각 움직이는 단계에서 마리드가 지정한 두 방향으로만 이동할 수 있다. 다오가 디지니를 만날 수 있는지 확인해야 한다. 만약 만날 수 있다면 디지니를 만나기 위해 움직인 방향들을 순서대로 출력해야 한다.

접근 방법

이 문제는, 디지니를 만나기 위한 최단경로를 찾을 필요는 없습니다. 어떠한 경로로 가던지 디지니를 만나기만 하면 되고, 만날 때까지의 움직임을 출력하면 됩니다. 따라서 '스페셜 저지'가 붙어있는 문제입니다.

다오는 움직일 때마다, 두 방향 중 하나를 골라야 합니다. 다오의 움직임을 '리프 노드를 제외한 각 노드가 2개의 자식 노드를 지니는 상태 공간 트리'로 생각해 볼 수 있습니다. N은 20 정도이기 때문에, 상태 공간 트리를 모두 탐색하다가, 디지니가 있는 곳에서 종료하고 답을 출력해주면 됩니다.

저는 문제를 잘 안 읽어서 중간에 종료를 안 하고, 상태 공간 트리를 끝까지 탐색하고 제일 짧은 경로를 출력했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 21;
int h, w, n, dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }, len = INT_MAX;
char m[MAX][MAX], rev[4] = {'W', 'D', 'S', 'A'};
bool visited[MAX][MAX];
pair<int, int> s;
vector<int> ans;

int convert(char c) {
	switch (c) {
	case 'W':
		return 0;
	case 'D':
		return 1;
	case 'S':
		return 2;
	case 'A':
		return 3;
	}
}

void func(vector<pair<int, int>>& v, vector<int>& path, pair<int, int> now, int idx) {
	if (m[now.first][now.second] == 'Z') {
		if (path.size() < len) {
			len = path.size();
			ans = path;
		}

		return;
	}

	if (idx == v.size())
		return;

	int nr = now.first + dir[v[idx].first][0];
	int nc = now.second + dir[v[idx].first][1];

	if (nr >= 1 && nr <= h && nc >= 1 && nc <= w && m[nr][nc] != '@') {
		path.push_back(v[idx].first);
		func(v, path, { nr, nc }, idx + 1);
		path.pop_back();
	}

	nr = now.first + dir[v[idx].second][0];
	nc = now.second + dir[v[idx].second][1];

	if (nr >= 1 && nr <= h && nc >= 1 && nc <= w && m[nr][nc] != '@') {
		path.push_back(v[idx].second);
		func(v, path, { nr, nc }, idx + 1);
		path.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			char c;
			cin >> c;

			if (c == 'D') {
				s = { i, j };
				m[i][j] = '.';
				continue;
			}

			m[i][j] = c;
		}
	}

	cin >> n;
	vector<pair<int, int>> v(n);
	for (auto& i : v) {
		char c1, c2;
		cin >> c1 >> c2;
		i = { convert(c1), convert(c2) };
	}

	vector<int> path;
	func(v, path, s, 0);
	if (len == INT_MAX) {
		cout << "NO\n";
		return 0;
	}

	cout << "YES\n";
	for (auto& i : ans)
		cout << rev[i];
	cout << '\n';
	return 0;
}