알고리즘

https://velog.io/@starkshn/%EC%84%A0%ED%98%95%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4xt40ba4#6-%EC%98%A4%EB%A5%B8%EC%86%90-%EB%B2%95%EC%B9%99-%EA%B0%9C%EC%84%A0

우수법 개선 하는 부분인데

기존의 쓸데없는 경로를 없애는 방법이다.

스택을 이용하여 경로를 "추적"하여 쓸데없는 경로는 pop으로 제거를 하여 경로를 만드는 부분이다 ❗❗

최단 거리는 아니지만, 나름 ㄱㅊ은듯??

동작이 어떻게 되는지 메모장으로 하나하나 다 보면서 이해를 하는게 처음에 좋은듯.

현재 1, 1 부터 시작을 하는데

1, 1,
2, 1,
3, 1,
4, 1,
5, 1,
5, 2,
5, 3,
6, 3,
7, 3,
7, 2,
7, 1,
7, 2,
7, 3,

에서

7, 3,
7, 2,
7, 1,
7, 2,
7, 3,
이부분 부터

이부분의 코드를 보면서

이렇게 i번째에서 스택과 check해야하는 부분 적어가면서 보면은 조금 이해가 된다.

이런식으로 하나하나 보도록 하자. 그러면 언제 pop이 두번 세번씩 되는지 이해가 조금 간다.