본문 바로가기

최소 스패닝 트리2

[프로그래머스 Lv4] : 지형 이동 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 칸에 방문하기 위한 사다리 설치 비용의 최솟값을 리턴해주자. 풀이 모든 칸에서 상하좌우로 이동할 수 있으며 높이 차가 주어진 height 값보다 작거나 같으면 그냥 이동할 수 있지만 높이 차가 height 보다 크다면 높이 차이만큼의 비용을 내고 사다리를 설치해야한다. 각 칸을 정점으로 봤을 때, 모든 정점을 이어지도록 하는 길을 찾아야한다는 뜻이다. 임의의 칸을 기준으로 상하좌우.. 2022. 7. 11.

[프로그래머스 Lv3] : 섬 연결하기 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 최소비용으로 n개의 섬이 모두 연결될 수 있도록 하는 문제. 풀이 다리를 통해서 통행이 가능하다면 두 섬은 연결되어있다고 본다. 문제를 보면 최소스패닝 트리 문제인 것을 알 수 있다. 최소 스패닝 트리를 이용해서 모든 섬이 공통 조상을 가지도록 연결시켜주면 된다. 코드 작성 #include #include #include using namespace std; const int MAX_N = 100 + 5; int Parent[MAX_N]; int F.. 2022. 6. 23.

이전 1 다음

티스토리툴바