알고리즘/programmers

[Programmers] 지형 이동

꾸준함. 2021. 10. 2. 00:54

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/62050

 

코딩테스트 연습 - 지형 이동

[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18

programmers.co.kr

크루스칼 알고리즘을 이용한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 사다리를 이용하지 않고 이동할 수 있는 지형들을 그룹핑해줍니다.

2. 그룹에서 다른 그룹으로 이동할 때 사용되는 사다리 비용을 구해주고 두 그룹과 함께 벡터에 넣어줍니다.

3. 2번에서 구한 벡터를 사다리 비용을 기준으로 오름차순 정렬을 해줍니다.

4. 크루스칼 알고리즘을 이용해 그룹을 합칠 때마다 사다리 비용을 결과에 더해줍니다.

5. 4번에서 구한 총비용을 반환해줍니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 행렬 테두리 회전하기  (0) 2021.10.02
[Programmers] 다단계 칫솔 판매  (0) 2021.10.02
[Programmers] 멀쩡한 사각형  (0) 2021.10.01
[Programmers] 쿠키 구입  (0) 2021.10.01
[Programmers] 지형 편집  (0) 2021.10.01