[BOJ C++] 1445 일요일 아침의 데이트

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

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

 

 

문제 이해

최대 50x50 크기의 숲의 지도가 주어지고 시작점과 도착점, 그리고 쓰레기가 표시되어 있습니다. 시작점에서 도착점까지 가야하며 쓰레기를 최대한 안거쳐서 가야하고, 또 쓰레기를 어쩔수 없이 거치게 된다면, 같은양의 쓰레기를 거친 경로중 쓰레기와 인접한 길을 최소한으로 해서 갔을 때 쓰레기를 거치는 것과, 인접한 쓰레기를 거치는 것이 최소로 되게 도착하였을 때의 횟수들을 구하는 문제였습니다.

 

 

입출력 조건

시간제한은 2초였으며, 숲의 좌우 넢이는 최대 50x50 이였습니다.

 

 

풀이

처음에는 단순 무식하게 bfs로 풀었습니다

큰 배열 2개를 잡고, 하나는 해당 좌표까지 이동할 때 거친 쓰레기의 갯수를, 또하나의 배열에는 해당 좌표까지 이동할 때 거친 주변 쓰레기의 갯수를 저장하며 bfs를 돌았습니다. 이렇게 구현하다가 잘 안되서 바람 좀 쐬고 왔는데 문득, 이럴거면 그냥 pq에 두개다 집어넣어서 저절로 나오게 하면 되지 않나..? 라는 생각을 하게 되었고 여태 했던거 싹 지웠습니다 ㅡㅡ^;;

 

pq에다가 쓰레기 갯수, 주변 쓰레기 갯수, y좌표, x좌표 를 넣어주면 쓰레기 갯수가 같을 때 주변 쓰레기 갯수를 비교해서 저절로 작은 값부터 나오게 되어 편하게 풀 수 있겠다 생각했고 그렇게 풀었습니다!

 

 

에러 및 느낀 점

구현력이 부족했던 것인지 첫번째 방법으로 잘 해결이 되지 않았었습니다.

그리고 두번째 방법으로는 마지막에 도착지점은 횟수에서 제외한다라는 조건을 제대로 인지하지 못해 계속 틀렸었습니다..

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1445_%EC%9D%BC%EC%9A%94%EC%9D%BC%20%EC%95%84%EC%B9%A8%EC%9D%98%20%EB%8D%B0%EC%9D%B4%ED%8A%B8.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.