오른손 법칙 개선

📌 기존 오른손 법칙의 문제점

• 우측 방향을 기준으로 가능한 경로를 계속 탐색
• 막다른 길이면 다시 되돌아가야 함
• 불필요한 경로가 path에 남게 됨

즉, 단순한 미로 길찾기는 가능하지만, 경로가 깔끔하지 않다.

---

💡 개선 아이디어

❗ 스택은 후입선출(LIFO)이기 때문에 "되돌아가는 경로"를 파악하고 제거하는 데 딱 알맞음!

1. 우리가 지나온 길을 stack<Pos>로 추적한다.
2. 다음 경로가 스택 최상단과 같다면, 방금 왔던 길로 돌아간 것 → pop()으로 제거!
3. 아니라면 진행 중인 새로운 경로이므로 → push()로 추가!
4. 최종적으로 스택에 남은 경로만 역순(reverse)하여 실제 경로로 사용.

---

🔁 오른손 법칙 + 스택 개선 알고리즘

✔️ 원본 경로(path)를 스택을 이용해 정제하는 코드

stack<Pos> s;

for (int i = 0; i < _path.size() - 1; i++)  // 마지막 목적지는 제외
{
    // 스택이 비어있지 않고, 현재 경로의 다음 지점이 스택 top과 같다면?
    // → 방금 왔던 길로 되돌아간 것! → pop() 해서 경로 제거
    if (!s.empty() && s.top() == _path[i + 1])
        s.pop();
    else
        s.push(_path[i]);  // 새 경로라면 push
}

// 마지막 목적지 처리
if (!_path.empty())
    s.push(_path.back());

---

✔️ 정제된 경로를 다시 벡터에 담기

vector<Pos> path;

while (!s.empty())
{
    path.push_back(s.top());
    s.pop();
}

// 스택은 후입선출 구조라 거꾸로 되어 있으므로 역순 정렬
std::reverse(path.begin(), path.end());

// 기존 경로를 정제된 path로 덮어쓰기
_path = path;

---

🎮 전체 알고리즘 흐름 요약

// 1. 오른손 법칙으로 _path에 경로를 저장
// 2. 스택을 사용해서 되돌아가는 경로 제거
// 3. 정제된 경로를 path에 저장 후 reverse
// 4. 최종 _path에 저장

---

🧠 핵심 원리 요약

단계	설명
1️⃣	s.top() == _path[i+1] 이면 되돌아가는 길 → pop()
2️⃣	아니면 새 길 → push()
3️⃣	스택에 남은 경로를 역순 정렬하여 실제 경로로 사용

간단하지만 강력한 방법! 스택의 후입선출 특성을 경로 추적에 적용한 완벽한 활용 예시!

---

📌 실제 적용 예시: Player::Init() 내 코드 일부

for (int i = 0; i < _path.size() - 1; i++)
{
    if (!s.empty() && s.top() == _path[i + 1])
        s.pop();
    else
        s.push(_path[i]);
}

if (!_path.empty())
    s.push(_path.back());

vector<Pos> path;
while (!s.empty())
{
    path.push_back(s.top());
    s.pop();
}

std::reverse(path.begin(), path.end());
_path = path;

---

🧪 결과 확인

이전에는 돌아갔다가 다시 오는 불필요한 경로까지 포함되어 있었다면,
이제는 경로가 훨씬 직관적이고 깔끔해짐!

❗ 단, 이 알고리즘은 최단 경로를 보장하진 않음.
❗ 하지만 되돌아가는 경로는 확실히 제거 가능!

---