[Algorithm] SWEA_알고스팟

최소 몇개 = 최단 기간 탐색 = 가중치 없음 = > BFS BFS하라는 말을 아주 돌려가면서.

우선순위 큐가 나오면 됨(원하는 녀석이 먼저 나오게 순위줘서 하자 그게 우선순위 큐를 사용한다.)

pq쓰면서 살펴볼 건 전 문제인 방향전환엔 큐에 넣으면서 방문 처리 했다. 그래서 신경 안쓰고 좋았는데 여기서 요소 찾고 pq.offer에서 방문처리 하면?

왜 아까랑 똑같이 안하고 밖으로 뺴서 사용 했을까?

안에다 쓰면 어떤 일이 일어나나?

발견하면서 방문처리 하면 나중에

큐에서는 담는 순으로 써도 되었는데

방문시점을 큐에 담을 때? 뺄때? 큐에 담았지만 그 녀석이 안 쓰일 수도 있다. (위 사진 경우 정중앙에서 그 옆에 갈 때) 사용순서는 pq에서 빠져 나올 때 결정

큐 쓰던거처럼 들어갈 때 방문처리 하면 내가 원하는 동잒때 방문처리 못할 수도 있다.

우선순위 큐는 방문 할 거다라고 하는거. 큐도 사실 맞는데 큐에선 쓸데없이 한번 더 돌아서 그렇고 pq까지 그렇게 하면 안된다.

방문처리를 언제 해야 하나!!

큐와 pq 잘 알아두자.

x,y좌표 관리하는데 부수는 횟수가 추가됨. 관리해야하는 객체가 가진 상태가 2개.

앞에서 봤던 문제처럼 3차원 배열처럼 관리하려 했는데 부순 횟수가 생각보다 많으면 공간복잡도가 너무 복잡해진다. 어떻게 이동할 지를 잠깐 그려보자

순서가 의미가 있었따.

한 뎁스에서 나와서 동작하는 녀석이 여러ㅐㄱ 있는데 원하는 녀석이 빨리 동작 원하는 녀석은 부순 횟수가 적은게 빨리 동작해야한다. 그런녀석 사용하기 위해 어떤걸 써야한다. 일반 큐는 횟수에 대한 관리가 안되서 우선순위 큐로 회수에 대한 제어를 해서 bfs를 돌렸다. 우선순위에 맞춰서 나올 것.

기본적인 코드는 똑같다(큐를 쓰나 pq를 쓰나. )

큐에 담을때 방문처리 되는게 아니라 뺴올 때 방문 처리가 된다.(주의! 꼭 기억!)