swea 1824. 혁진이의 프로그램 검증

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE

SW Expert Academy

[풀이]

bfs를 사용해서 풀었다.

각 명령어마다 수행할 일을 if문으로 구현했다.

visited배열을 사용하여 같은 루트는 가지 않도록 했다.

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
	int d;//방향
	int m;//메모리
};

int T;
int R, C;
char Cmd[20][20];
bool visited[20][20][4][16];
const int dx[] = { -1,1,0,0 };//0:위, 1:아래
const int dy[] = { 0,0,-1,1 };//2:왼, 3:오
int mem = 0;

bool bfs() {
	queue<Pos>q;
	q.push({ 0,0,3,0 });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		int m = q.front().m;
		q.pop();
		//'@'일 때
		if (Cmd[x][y] == '@')
			return true;
		//'<'일 때
		else if (Cmd[x][y] == '<')
			d = 2;
		//'>'일 때
		else if (Cmd[x][y] == '>')
			d = 3;
		//'^'일 때
		else if (Cmd[x][y] == '^')
			d = 0;
		//'v'일 때
		else if (Cmd[x][y] == 'v')
			d = 1;
		//'-'일 때
		else if (Cmd[x][y] == '_')
			if (m == 0)
				d = 3;
			else
				d = 2;
		//'|'일 때
		else if (Cmd[x][y] == '|')
			if (m == 0)
				d = 1;
			else
				d = 0;
		//0~9일 때
		else if (Cmd[x][y] - '0' >= 0 && Cmd[x][y] - '0' <= 9)
			m = Cmd[x][y] - '0';
		//'+'일 때
		else if (Cmd[x][y] == '+') {
			if (m == 15)
				m = 0;
			else
				m++;
		}
		//'-'일 때
		else if (Cmd[x][y] == '-') {
			if (m == 0)
				m = 15;
			else
				m--;
		}
		//'?'일 때
		if (Cmd[x][y] == '?') {
			for (int i = 0; i < 4; i++) {
				if (visited[x][y][i][m] == true)
					continue;
				visited[x][y][i][m] = true;
				int nx = (x + dx[i]+R)%R;
				int ny = (y + dy[i]+C)%C;
				q.push({ nx,ny,i,m });
			}
		}
		else if (visited[x][y][d][m] == false) {
			visited[x][y][d][m] = true;
			int nx = (x + dx[d] + R) % R;
			int ny = (y + dy[d] + C) % C;
			q.push({ nx,ny,d,m });
		}
	}
	return false;
}

void solution() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(visited, false, sizeof(visited));
		cin >> R >> C;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				cin >> Cmd[i][j];
			}
		}
		bool res = bfs();
		if (res == true)
			cout << '#' << t << " YES\n";
		else
			cout << '#' << t << " NO\n";
	}
}

int main() {
	solution();
	return 0;
}