소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <tuple>

using namespace std;

typedef tuple<int, int, int, int> state;

const int dy[] = { -1, +1, 0, 0 };
const int dx[] = { 0, 0, -1, +1 };

int R; // 세로 크기
int C; // 가로 크기
vector<string> map; // 격자

int input() 
{
	cin >> R >> C;
	map.assign(R, "");
	for (int r = 0; r < R; ++r) cin >> map[r];

	int valid = 0;
	for (const auto& s : map)
	{
		for (const auto& c : s)
		{
			if (!valid && c == '@') valid = 1;
		}
	}

	if (valid) return 0;
	else return -1;
}

string solve() 
{
	string answer = "NO";

	if (input() < 0) 
	{
		answer = "NO";
	}
	else
	{
		state init = make_tuple(0, 0, 3, 0); // 좌상단 위치, 오른쪽 이동방향, 메모리 0
		queue<state> q; q.emplace(init); // 큐에 삽입
		vector<vector<vector<vector<int> > > > visited(R, vector<vector<vector<int> > >(C, vector<vector<int> >(4, vector<int>(16, 0))));
		visited[0][0][3][0] = 1; // 방문처리

		while (!q.empty())
		{
			int cy, cx, dir, mem;
			tie(cy, cx, dir, mem) = q.front(); q.pop();
			char c = map[cy][cx];

			if (c == '<') dir = 2;
			else if (c == '>') dir = 3;
			else if (c == '^') dir = 0;
			else if (c == 'v') dir = 1;
			else if (c == '_') mem == 0 ? dir = 3 : dir = 2;
			else if (c == '|') mem == 0 ? dir = 1 : dir = 0;
			else if ('0' <= c && c <= '9') mem = c - '0';
			else if (c == '+') mem == 15 ? mem = 0 : mem += 1;
			else if (c == '-') mem == 0 ? mem = 15 : mem -= 1;
			else if (c == '@')
			{
				answer = "YES";
				break;
			}

			if (c == '?')
			{
				int cnt = 0;
				for (int d = 0; d < 4; ++d)
				{
					dir = d;
					int ny = (cy + dy[dir] + R) % R;
					int nx = (cx + dx[dir] + C) % C;
					if (visited[ny][nx][dir][mem])
					{
						continue;
					}
					else
					{
						visited[ny][nx][dir][mem] = 1;
						q.emplace(ny, nx, dir, mem);
						cnt += 1;
					}
				}

				if (cnt == 0)
				{
					continue;
				}
			}
			else
			{
				int ny = (cy + dy[dir] + R) % R;
				int nx = (cx + dx[dir] + C) % C;
				if (visited[ny][nx][dir][mem])
				{
					continue;
					break;
				}
				else
				{
					visited[ny][nx][dir][mem] = 1;
					q.emplace(ny, nx, dir, mem);
				}
			}
		}
	}

	return answer;
}

int main()
{
	//freopen("sample_input_swea_1824.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; ++tc)
	{
		cout << "#" << tc << " " << solve() << endl;
	}

	return 0;
}

해설

핵심은 기본 BFS 구조에 (1) 순환을 어떻게 잡아낼 것인지, (2) ? 문자의 경우 어떻게 처리할 것인지 이다.
(1) 순환 잡아내기
순환의 경우 같은 위치에, 같은 방향, 같은 메모리 값으로 되돌아 왔을 경우 순환이라고 판단할 수 있으므로 4차원 방문배열을 사용하도록 한다.

(2) ? 문자 처리하기
? 문자의 경우 랜덤으로 4방향 중 한 곳으로 간다고 했으므로 4방향 탐색 반복문을 짜도록 한다. 이때 바로 방문로직과 큐 삽입 로직을 수행해야 하므로 다른 케이스와 구분하여 구현하도록 한다.