백준 3987번 보이저 1호 C++

출처 : https://www.acmicpc.net/problem/3987

 

visited 배열을 이용했는데, bool이 아닌 int로 사용하였다. 아무것도 없는 공간은 가로로 간 곳을 세로로 다시 갈 수 있기 때문에 고려하지 않았고, /와 \인 경우만 고려했는데, /의 경우에는 왼쪽과 위쪽에서 오는 경우 visited를 1로 하고, 오른쪽과 아래쪽에서 오는 경우는 visited를 2로 하였다. 백슬래시의 경우에도 선을 기준으로 왼쪽은 1, 오른쪽은 2로 하였다.

visited가 1일 때 1로 설정한 곳에서 오거나 2일때 2로 설정한 곳에서 오면 무한히 반복되는 것이다. 그리고 visited가 3이면 양쪽 다 이미 들린 상태에서 또 들린 것이기 때문에 이것도 무한히 반복된다. 이걸 구현하는 게 쉽지는 않았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

int n, m, pr, pc;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
char chars[4] = { 'U','R','D','L' };
const int INF = 987654321;

int SetDir(int dir, char sig) {
	int ret = dir;
	if (sig == '/') {
		if (dir == 0) ret = 1;
		if (dir == 1) ret = 0;
		if (dir == 2) ret = 3;
		if (dir == 3) ret = 2;
	}
	else {
		if (dir == 0) ret = 3;
		if (dir == 1) ret = 2;
		if (dir == 2) ret = 1;
		if (dir == 3) ret = 0;
	}
	return ret;
}

int solve(int dir, const vector<vector<char>>& board) {
	vector<vector<int>> visited(n + 1, vector<int>(m + 1, 0));
	int row = pr;
	int col = pc;
	int ret = 0;
	while (true) {
		ret++;
		int nextRow = row + dRow[dir];
		int nextCol = col + dCol[dir];
		if (nextRow<1 || nextRow>n) break;
		if (nextCol<1 || nextCol>m) break;
		char nextChar = board[nextRow][nextCol];
		if (nextChar == 'C') break;
		if (nextChar == '/' || nextChar == '\\') {
			int& visit = visited[nextRow][nextCol];
			if (visit == 0) {
				if (nextChar == '/') {
					if (dir == 1 || dir == 2) visit = 1;
					if (dir == 0 || dir == 3) visit = 2;
				}
				else {
					if (dir == 0 || dir == 1) visit = 1;
					if (dir == 2 || dir == 3) visit = 2;
				}
			}
			else if (visit == 1) {
				if (nextChar == '/') {
					if (dir == 1 || dir == 2) {
						ret = INF;
						break;
					}
					if (dir == 0 || dir == 3) visit = 3;
				}
				else {
					if (dir == 0 || dir == 1) {
						ret = INF;
						break;
					}
					if (dir == 2 || dir == 3) visit = 3;
				}
			}
			else if (visit == 2) {
				if (nextChar == '/') {
					if (dir == 1 || dir == 2) visit = 3;
					if (dir == 0 || dir == 3) {
						ret = INF;
						break;
					}
				}
				else {
					if (dir == 0 || dir == 1) visit = 3;
					if (dir == 2 || dir == 3) {
						ret = INF;
						break;
					}
				}
			}
			else if (visit == 3) {
				ret = INF;
				break;
			}
			dir = SetDir(dir, nextChar);
		}
		row = nextRow;
		col = nextCol;
	}
	return ret;
}

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

	cin >> n >> m;
	vector<vector<char>> board(n + 1, vector<char>(m + 1));
	for (int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= m; j++) {
			board[i][j] = str[j - 1];
		}
	}
	cin >> pr >> pc;
	int ans = -1;
	char ch = 'N';
	for (int i = 0; i < 4; i++) {
		int ret = solve(i, board);
		if (ret > ans) {
			ans = ret;
			ch = chars[i];
		}
	}
	cout << ch << "\n";
	if (ans == INF) cout << "Voyager";
	else cout << ans;
};