1445. 일요일 아침의 데이트

골드 재활 중~

1445번: 일요일 아침의 데이트

---

대충 쓰레기를 최대한 피해서 목적지에 도달하면 되는 문제이다. 그런데 지문이 진짜 쓰레기 수준이라 제대로 읽지 않으면 틀리기 매우 쉽다. 함께 자세히 읽어 보자.

1. 쓰레기를 밟지 않는 것을 우선으로 해야 한다. 쓰레기 옆을 지나가는 건 그 다음이다.
2. 쓰레기 옆을 지나가는 행동의 기준은 a) 비어있는 칸을 지나가는데 b) 그 칸의 상하좌우에 쓰레기가 있는 경우이다. 따라서 쓰레기가 있는 칸 옆에 쓰레기가 있다면 쓰레기 옆을 지나가는 것으로 판정하지 않는다. 그건 그냥 쓰레기를 밟고 지나가는 경우이다.
3. 출발점과 도착점은 비어 있는 칸이 아니다. 따라서 출발점 또는 도착점 주변에 쓰레기가 있더라도 쓰레기 옆을 지나가는 것으로 판정하지 않는다.

위의 내용에 주의하면서 우선순위 큐 bfs를 구현하면 된다.

 

다익스트라까지 구현할 필요는 없다. 오히려 가중치를 만드는 게 더 어려울 것이다. 다익스트라에 우선순위 큐가 쓰이기 때문에 많이들 혼동하는데, 다익스트라 없이 우선순위 큐만 사용해도 해결할 수 있다.

---

지문 낚시 때문에 골2인 문제. 낚시 없었다면 골3이 적정.