[백준 20419] 화살표 미로 (Easy) (C++)

문제 링크: www.acmicpc.net/problem/20419

20419번: 화살표 미로 (Easy)

1. 주의할 점

- 주문서는 최대 1개 가질 수 있다

- 주문서는 왼쪽, 오른쪽 회전 1개가 세트다

 

2. 구현

- 미로를 입력받으면서 Check[][] 배열을 3으로 초기화시킨다. Check[][] 배열은 해당 지점에 몇개의 주문서를 사용해서 도착했는가?에 대한 정보를 담고있다 -> 시간절약위해 사용

- DFS()를 수행하며, 변수로는 Y, X, 사용한 오른쪽회전 주문서 갯수, 사용한 왼쪽회전 주문서 갯수를 입력받는다

- DFS에는 이미 도착지점에 도달한적이 있거나(Avail==true), 현재 지점이 도착지점이면 Avail=true로 바꾼 후, Return 수행한다

- 현재 지점의 미로방향을 확인하고 그대로 진행, 오른쪽으로 회전 후 진행(r<paper일 때), 왼쪽으로 회전 후 진행(l<paper일 때) 총 3가지 방향을 확인한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
char arr[51][51];
int check[51][51];
int row, col, paper;
bool avail = false;

void dfs(int y, int x, int r, int l) {
	if (avail) return;
	int use = max(r, l);;
	check[y][x] = use;
	if (x == col && y == row) {
		avail = true;
		return;
	}
	char c = arr[y][x];
	int dir, nd;
	if (c == 'U') dir = 0;
	else if (c == 'R') dir = 1;
	else if (c == 'D') dir = 2;
	else dir = 3;
	int nx = x + dx[dir];
	int ny = y + dy[dir];
	if (nx > 0 && ny > 0 && nx <= col && ny <= row && check[ny][nx] > use)
		dfs(ny, nx, r, l);
	//회전
	if (r < paper) {
		//오른쪽
		nd = (dir + 1) % 4;
		nx = x + dx[nd];
		ny = y + dy[nd];
		if (nx > 0 && ny > 0 && nx <= col && ny <= row && check[ny][nx] > use + 1)
			dfs(ny, nx, r + 1, l);
	}
	//왼쪽
	if (l < paper) {
		nd = (dir + 3) % 4;
		nx = x + dx[nd];
		ny = y + dy[nd];
		if (nx > 0 && ny > 0 && nx <= col && ny <= row && check[ny][nx] > use + 1)
			dfs(ny, nx, r, l + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> paper;
	for(int i=1;i<=row;i++)
		for (int j = 1; j <= col; j++) {
			cin >> arr[i][j];
			check[i][j] = 3;
		}
	dfs(1, 1, 0, 0);
	avail ? cout << "Yes" : cout << "No";
	return 0;
}