첫 알고리즘 포스팅입니다. 잘 부탁드립니다.
2017.10.29 **,주말의 끝 일요일 ** Solution - 2665(미로 만들기)
풀이방법: 다익스트라
문제 해석
다익스트라의 일반적인 문제와 스타일이 비슷하다.
각 칸마다 지금까지 검은 벽을 지나온 개수들을 카운트 해준다. 최소화로 말이다.
풀이 방식
1. 초기화를 진행한다. dist의 초기 값은 0으로 셋팅한다.
2. 우선순위 큐를 설계한다. 값의 비교가 필요하니, 3개의 값을 가진 클래스를 설계한다.
3. 큐에 초기화가 적용된 출발 노드를 삽입한다.
4. 동작배열을 활용하여 상하좌우를 검색한다.
5. 조건을 나눈다. 1) 빈칸 2)검은색칸 이렇게 나눠서 계산한다.
6. 빈칸일경우 이전칸과 지금칸중에 가장 검은색칸을 적게 지나온 것으로 셋팅한다.
7. 검은칸일경우 지금의 칸을 지나는게( +1) 현재칸이 지나온 검은색칸보다 작다면 셋팅한다.
8. 현재의 칸에 대한 방문배열값을 true로 바꾼다.
9. while이 끝나고 값을 출력한다.
사실 이번 문제 같은 경우에는 딱히 해설이 필요없습니다. 단순히 다익스트라만 알면 풀수 있는 문제이고,
주의할점이 있다면 조건을 잘 나눠야하는것 밖에 없습니다.. 그래서 조금 해설이 정성이 부족한것도 있습니다.
궁금한점 있으시거나, 피드백을 해주실 분들은 댓글 달아주세요 !
(당부의 말씀 : 저는 고민을 먼저하고 문제를 풉니다. 다풀고나서 채점을 통해 맞으면 맞는거고, 틀리면 수정을 합니다. 하지만 저는 저만의 풀이가 끝나고 다른 사람들의 풀이와 비교를 통해 최적의 풀이방법을 찾으려 노력을 하고 있습니다. 만약 마지막 수정중에 다른분들것과 너무 흡사 하면 출저를 달아놓겠습니다.)
'알고리즘(추가예정) > 다익스트라' 카테고리의 다른 글
| 백준 1238 파티 (0) | 2017.11.02 |
|---|