어흥
[백준 20419] 화살표 미로 (Easy) (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/20419
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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 2096] 내려가기 (C++) (0) | 2021.01.07 |
---|---|
[백준 20422] 퀼린드롬 (Easy) (C++) (0) | 2021.01.04 |
[백준 11660] 구간 합 구하기 5 (C++) (0) | 2020.12.30 |
[백준 20005] 보스몬스터 전리품 (C++) (0) | 2020.12.27 |
[백준 13908] 비밀번호 (C++) (0) | 2020.12.24 |
Comments