[Algorithm] SWEA_알고스팟

문제 유형 파악

• “최소 몇 개” = “최단 기간 탐색” = “가중치 없음” ⇒ BFS
• 결국 BFS를 하라는 말을 아주 돌려서 표현한 것이다.

우선순위 큐(PQ)를 언제 쓰나

원하는 녀석이 먼저 나오게 순위를 줘서 처리해야 한다면 우선순위 큐(Priority Queue) 를 쓴다.

PQ를 쓰면서 살펴볼 점은, 전 문제인 「방향전환」에서는 큐에 넣으면서 방문 처리를 했다는 것이다. 그때는 신경 쓸 게 없어 편했는데, 여기서는 요소를 찾고 pq.offer 시점에 방문 처리를 하면 어떻게 될까?

왜 「방향전환」처럼 (담을 때) 처리하지 않고, 방문 처리를 밖으로 빼서 사용했을까? 안에다 쓰면 어떤 일이 일어나나?

발견하면서(담을 때) 방문 처리를 하는 경우

발견하면서 방문 처리를 하면 나중에 문제가 생긴다. 일반 큐에서는 담는 순서대로 써도 되었다.

방문 시점을 담을 때로 잡으면 생기는 문제

방문 처리는 언제 해야 하나

• 방문 시점을 큐에 담을 때로 할지, 뺄 때로 할지가 핵심이다.
• 큐에 담았더라도 그 녀석이 끝내 안 쓰일 수도 있다. (위 사진의 정중앙에서 그 옆으로 갈 때의 경우)
• 사용 순서는 PQ에서 빠져나올 때 결정된다.
• 일반 큐처럼 들어갈 때 방문 처리를 하면, 내가 원하는 동작 시점에 방문 처리를 못 할 수도 있다.

우선순위 큐는 “방문할 거다”라고 미리 정해 두는 것이다. 큐로도 사실 맞게 풀 수는 있지만, 큐에선 쓸데없이 한 번 더 돌게 되고, PQ까지 그런 식으로 하면 안 된다.

방문 처리를 언제 해야 하나!! 큐와 PQ를 잘 알아두자.

관리해야 하는 상태

• x, y 좌표를 관리하는데 여기에 “부수는 횟수”가 추가된다. ⇒ 관리해야 하는 객체의 상태가 2개.
• 앞 문제처럼 3차원 배열로 관리하려 했는데, 부순 횟수가 생각보다 많으면 공간복잡도가 너무 복잡해진다.
• 어떻게 이동할지를 잠깐 그려보자. 여기서는 순서가 의미가 있었다.

왜 우선순위 큐인가

• 한 뎁스에서 나와 동작하는 녀석이 여러 개 있는데, 원하는 녀석(= 부순 횟수가 적은 것)이 빨리 동작해야 한다.
• 일반 큐는 (부순) 횟수에 대한 관리가 안 된다.
• 그래서 우선순위 큐로 횟수에 대한 제어를 해서, 우선순위에 맞춰 나오도록 BFS를 돌렸다.

기본적인 코드는 큐를 쓰나 PQ를 쓰나 똑같다. 주의! 꼭 기억! 큐에 담을 때 방문 처리가 되는 게 아니라, 빼올 때 방문 처리가 된다.