백준 BOJ(1445) 일요일 아침의 데이트

문제:

https://www.acmicpc.net/problem/1445

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

 

풀이:

 

우선 주의할점은 '만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다' 이 부분이다.

 

칸이 비어있는 경우에만 인접한 칸에 쓰레기를 검사해야 한다. 

 

priority queue를 이용해서 { 밟은 쓰레기, 인접 쓰레기 } , { y , x} 를 오름차순 pq로 만들자 그러면 자동으로

 

pq에서 꺼내는 것은 밟은 쓰레기가 가장 적고 밟은 쓰레기가 동일하다면 인접 쓰레기가 가장 적은 후보이다.

 

이 후보가 F에 도달했다면 그 즉시 종료한다.

 

코드 (C ++ )