
[C++] 백준 1445번 : 일요일 아침의 데이트
·
problem solving/백준
🔗 문제 https://www.acmicpc.net/problem/1445 ✏️ 풀이문제를 잘 읽어야 하므로 특. 별. 히 캡처를 해왔습니다. 저는 노란 부분만 잘 읽으면 된다고 생각하고 난이도도 골4라고 생각됩니다. 구현 문제는 정리를 하고 풉니다. [나는 무엇을 구현해야하는가?]2차원 배열에서 출발지가 주어지고 '쓰레기칸', '쓰레기인접칸'을 최소로 밟고 목적지까지 도달하는 것.출발지와 목적지가 주어져있고, 재방문 여부와 상관없이 가중치만 최소로 해야 한다. -> 다익스트라 이렇게 차분히 생각하면 알고리즘을 특정할 수 있고 문제가 쉬워집니다. [조금의 최적화]특정 위치가 쓰레기 인접칸인지 확인하려고 매번 4방 탐색을 한다?같은 칸을 여러 번 방문하는 다익스트라 특성상 비효율적입니다. 쓰레기위치..