[ 백준 1197 : 최소 스패닝 트리 ]
그래프를 준다.
그리고 각 간선에는 가중치가 주어진다. 방향성은 없다.
모든 노드를 연결하는 간선들 가중치의 합을 출력하면된다.
최소 스패닝 트리를 만드는 가장 쉬운 알고리즘을 소개한다.
크루스칼 알고리즘인데 구현하기가 매우 쉽고 빨라서 많이들 MST문제를 풀 때 크루스칼을 쓰는것같다.
알고리즘 구현 순서는
1. 간선의 정보를 입력받는다.
2. 오름차순으로 정렬을한다.
3. 작은 간선부터 차례대로 이어본다.
4. 만약 간선을 이었을때!!! 1-2-3-1-2-3-1-2-3 .. 이런식으로 반복되는. 싸이클을 도는 간선이라면 건너뛴다.
5. 간선을 N-1개를 연결했으면 지금까지 연결한 간선들이 최소 스패닝 트리가 된다.
진짜 쉽고 간단하다..
근데 제일 문제점은 간선을 이었을때 이게 싸이클을 도는지 안도는지를 확인하는 방법을 알아야한다.
유니온 파인드라는 방법을 많이 사용하는데
이런식이다.
1. 노드의 갯수만큼 배열을 선언한다.
2. 이 배열들은 모두 -1 같은 어떤 초기 값을 가지고 있는다. 이 초기값은 노드값이 될 수 없어야한다.
3. 1과 2 노드를 연결하는 간선을 만들어본다고하자.
그럼 ARRAY[1] = 1, ARRAY[2]=1 이런식으로 한 숫자를 바라보게한다.
다시 2와 3을 연결한다? 그럼 ARRAY[2] = 1는 이미 설정되어있다. ARRAY[3] = ARRAY[2] = 1 이렇게 재귀적으로 들어가 한 점을 바라보게 하면된다!!
그럼 이제 싸이클이 도는지 안도는지를 확인하는 방법은 ARRAY[X] != ARRAY[Y] 이면 아직 다른 컴포넌트임을 보여준다.
코드로 표현하면 더 쉽게 볼 수 있다.
아무튼 이 문제는
크루스칼 알고리즘 기초문제다.
가중치를 기준으로 오름차순 정렬을 한 후 가중치가 작은 간선부터
한개씩 연결하면된다!!
이 블로그 검색
피드 구독하기:
댓글 (Atom)
-
[ 백준 1024 : 수열의 합 ] 간만에 푼 백준~ 쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다. 만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 ...
-
[백준 1091 : 카드 섞기 ] 이 문제도 5달 전에 풀었다가 포기했었던 문제였나보다. 오늘 틀렸던 문제 다시풀기 중 풀게 되었다. 문제를 읽는데 헷갈려서 머리카락 한 10번은 쥐어짠듯. 아마 전에 풀었을때는 P배열이 각 카드가 최후에 ...
-
아마 나와 비슷한 나이대의 학생들은 대부분 대학에서 수업을 들으면서 꾸준하게 들었을 것 같다. 물론 내가 그래서 그렇다. 4차산업~ IT의 시대~ 빅데이터~ 데이터 마이닝~ 하지만 컴퓨터 관련 전공자가 아니고 더군다나 공학 계열 전공자가 아니라...
[백준 16236] 아기 상어
[ 백준 16236 : 아기 상어 ] 2018 삼성전자 sw직무 하반기 기출문제입니다. 역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다. 저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 ...
댓글 없음:
댓글 쓰기