[Algorithm] SWEA_방향전환

bfs는 가중치가 없을때만 가능. 가중치 있으면 그리디한 다익스트라 다익스트라도 음수가 있으면 안됨. 음의 가중치면 벨만포드 쓰면 되지만 얘는 거의 고려 안하고 음의 가중치도 웬만해서 고려 안함.

다익스트라는 한 정점에서 다른 모든 정점 간의 최단거리 구할 때 다익스트라를 쓸 수 있다.

n개의 정점에서 n개로 갈때 플루이드 워셜 사용 가능(N:N) 얘도 최대의 단점은 시간 복잡도(무려 시간복잡도가 n3) 노드의 개수가 1000개 미만인 경우만 한번 생각하고 시도해 볼만 하다.

그 속성을 처리 했냐 = visited

방문 하면 재방문 안하나? ex)유럽 개선문 갔는데 가봤다고 또 유럽 안갈거?

한번 세로로 내려오면 가로 , 가로로 내려오면 세로로 가야한다. 어떤 지점이 있을 때.

우리가 관리해야하는 속성이 3개다(말과 원숭이와 비슷한 문제.)

어떤방향으로 해도 된다. = 그냥 모든 방향 다 해봐야 한다.

문제를 푸는 법은 완탐에서 출발해라. 완탐으로 해서 하는게 가장 권장이 된다.

규칙 찾아서 그리디 한 방법으로 해도 되지만 완탐으로 해서 범용성 있게 푸는게 더 권장이 된다.

여기서 중요한 건 내가 관리해야할 상태가 하나가 더 있다는 거(3차원 배열) 관리해야할 상태가 4개면 4차원 배열 써야 할 떄도 있다.. ㅠㅠㅠ 근데 그러면 공간 복잡도가 너무 커진다. 그냥 쪼개서 관리하는게 유리하다. 아무튼 중요한건 관리해야 할 속성이 늘어나면 관리 해줘야 한다. (달이차오른다 가자, 벽 뿌수기, 말과 원숭이 이런 문제들도 비슷하다.)