이거 크루스칼로 풀어도 풀리는데 맞는건가요?
const p = [
[1, 2, 6],
[1, 3, 3],
[3, 2, 2],
[2, 4, 1],
[2, 5, 13],
[3, 4, 5],
[4, 2, 3],
[4, 5, 7],
];
solution(p, 5, 8);
function solution(p, city, line) {
p.sort((a, b) => a[2] - b[2]);
const unf = Array(city + 1).fill(0);
for (let i = 0; i < city + 1; ++i) unf[i] = i;
function find(v) {
if (v === unf[v]) return v;
else return (unf[v] = find(unf[v]));
}
function union(f1, f2) {
const c1 = find(f1);
const c2 = find(f2);
if (c1 != c2) {
unf[c1] = c2;
return true;
}
return false;
}
let cost = 0;
for (let i = 0; i < p.length; ++i) {
const [c1, c2, val] = p[i];
if (union(c1, c2)) {
cost += val;
}
}
return cost;
}
크루스칼로 풀어도 풀리는데
이것도 맞는 풀이인가요?
테스트 케이스가 더 잇엇으면 좋겟네요
답변 1
1
안녕하세요^^
문제가 모든 정점에서 모든 정점으로 가는 최소비용을 각각 2차원 배열에 구하라는 의미입니다. 영상처럼 2차원 배열 dist에 각각 최소비용를 구해야 합니다. dist[i][j] 값의 의미는 i번 정점에서 j번 정점으로 가는 최소비용입니다. 답을 2차원 배열로 구하는 플로이드 워샬 차제를 많이 연습하세요. 플로이드 워샬을 통해 구한 2차원 최소비용 배열을 이용해 문제를 해결하는 응용문제가 요즘 많이 나옵니다.
87번 채점 프로그램에 오류가 있는 것 같습니다.
0
91
2
그리디 파트
0
115
2
안녕하세요. 선생님(54번 코드 관련 문의)
0
143
2
테스트 파일 exit_coe_1, time_limit_exceeded 질문
0
143
1
C언어로 코드를 짜면 채점 시에 한 문제 빼고 시간 초과가 발생하는데 해결하는 방법이 있을까요?
0
173
1
19번 질문있습니다
0
123
1
6번 관련 채점오류입니다
0
88
2
22번 문제는 C로 풀어주신 건가요 C++로 풀어주신 건가요?
0
166
2
dev C++ 콘솔창 바로 닫힘
0
245
1
최신화하기
0
171
1
채점이 안되요...
1
261
1
안녕하세요 강사님 정렬에 대해서 설명이 조금 더 듣고 싶습니다.
0
113
1
45번 공주구하기 문제를 list를 이용해서 이렇게 풀어도 될까요?
0
155
1
39번 두 배열 합치기 문제 채점 오류인가 코드 오류인가
0
155
0
채점기에서 틀렸다고 나오는데 이유를 모르겠습니다.
0
150
2
해당 강의에서 C언어로만 진행하는 강의 문의 건
0
145
2
87번 문제 섬나라 아일랜드 질문
0
128
1
16번 문제에서 직접 답을 대입하면 정답이 나오는데 채점에서 wrong answer가 나옵니다.
0
149
1
40번 교집합 문제
0
166
1
43번 뮤직비디오 문제 테스트케이스 4번을 만족 못합니다.
0
170
1
41. 연속된 자연수의 합 문제 질문있습니다.
0
166
1
질문있습니다.
0
193
2
시간초과가 나요
0
172
1
43번 문제 3 ~ 5번에 문제가 있는것 같습니다.
0
249
1





