#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, K, L;
int map[102][102]; // 1, 1부터 N, N까지 주의
int vis[102][102];
vector<pair<int, char>> infor;
int dr[4] = { -1, 0, 1, 0 }; //방향 정보 0:북 1: 동 2: 남 3: 서
int dc[4] = { 0, 1, 0, -1 };
bool fin; //벽 부딪혔는 지 체크
int state = 1; //방향 정보 0:북 1: 동 2: 남 3: 서
int cnt; //초
int idx; //방향 변환 정보 인덱스
int len = 1;
queue < pair<int, int>> tail; //발자취 정보 : front가 꼬리
void dfs(int r, int c) {
if (idx < L) { // idx를 지속적으로 높이면 아래 배열 참조할 때 참조에러
if (cnt == infor[idx].first) {
if (infor[idx].second == 'L') {
state = (state - 1) % 4; // -1 % 4 = -1 (3을 의도)
if (state < 0) //음수일 때, 따로 처리
state += 4;
}
else if(infor[idx].second == 'D')
state = (state + 1) % 4;
idx++;
}
}
int nr = r + dr[state];
int nc = c + dc[state];
if (nr <= 0 || nc <= 0 || nr > N || nc > N || vis[nr][nc]) { //벽 부딪치거나 자기 몸에 닿을 때
fin = true;
cnt++;
return;
}
if (map[nr][nc] == 1) { //사과 있으면
vis[nr][nc] = 1; //앞으로 전진
map[nr][nc] = 0; //사과 먹기
tail.push({ nr, nc }); //발자취 추가
cnt++; //초 증가
len++; //몸 길이 증가
dfs(nr, nc);
}
else { //사과 없으면(독립적이므로 if, else)
tail.push({ nr, nc }); //발자취 추가
if (len < tail.size()) { // 원래 길이보다 길어진다면
vis[tail.front().first][tail.front().second] = 0; //꼬리 없애기
tail.pop(); // 벡터에서 삭제
}
vis[nr][nc] = 1; //앞으로 전진
cnt++; //초 증가
dfs(nr, nc);
}
}
int main() {
cin >> N >> K;
int a, b;
for (int i = 0; i < K; i++) {
cin >> a >> b;
map[a][b] = 1; //사과 위치
}
cin >> L;
char c;
for (int i = 0; i < L; i++) {
cin >> a >> c;
infor.push_back({ a, c }); // 방향 변환 정보
}
tail.push({ 1,1 });
vis[1][1] = 1;
dfs(1, 1);
cout << cnt << endl;
}1. 방향 변환 정보의 X는 누적된 시간
- 초를 세면서 방향 변환 정보에서 현재 idx가 가리키는 X값과 같아지면 state를 변경
- ※ idx 계속 더하면 if문에서 지속적으로 조건 확인하기 때문에 벡터 크기를 초과한 셀을 방문 하면 에러가 발생
2. 4 방향을 탐색하는 게 아니라, 상태 유지를 하면서 전진해야 함 (state변수 이용)
- 90도 방향 전환은 +,- 와 %로 가능 (단, %가 음수를 처리하지 못하므로 음수일 땐 더하기 처리해주어야 함)
3. 발자취 추적은 queue 하나로 가능
- 나아가면서 추가하고 길이 유지하면서 front로 꼬리를 자를 수 있음