반갑습니다!

1647번: 도시 분할 계획 boj.kr 풀이 이 문제는 최소한의 비용으로 두 마을을 만들어야하는데, 결국 1개의 최소 스패닝 트리를 만들고 그 중에 가장 큰 간선을 제거해주면 최소한의 비용으로 2개의 마을을 만든 것과 같다. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어서 해결하였다. 코드 C++ #include #include #include using namespace std; int n, m; vector edges; vector root; int find(int v) { if (root[v] != v) root[v] = find(root[v]); return root[v]; } void merge(int a, int b) { a = find(a); b = find(b); if (a < ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 크게 3단계로 풀이된다. 사다리 설치가 필요없는 지형들 그룹화 그룹화된 지형들 사이를 이동하는 최소 비용 저장 저장된 최소 비용들로 MST 생성 1. 사다리 설치가 필요없는 지형들 그룹화 DFS 혹은 BFS를 사용하여 사다리가 필요없이 이동가능한 지형들을 하나의 그룹으로 표시한다. 아래의 코드에서는 방문 여부를 체크하는 visited배열을 int형으로 선언하여 방문 여부의 체크와 그룹 표시를 같이 진행하였다. 2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장 visited배열에 그룹을 구..