3주차 (2021년 01월 13일)

목표

• 인프런 파이썬 강의 1시간 수강

• 수강 후 내용 실습

• 알고리즘 < 최소 스패닝트리 > 문제풀기 (백준 1197번)

회고

• 인프런 파이썬 강의 40분 수강

• 배운 내용 jupyter notebook을 사용해서 실습

공부한 내용 : Python의 자료구조(리스트, 사전, 튜플, 세트, 자료구조의 변경)

• 알고리즘 < 최소 스패닝트리 > 문제 : 백준 1197번(“최소 스패닝트리”) -> 난이도 : 골드4

해결 방법 : 기본적으로 union-find를 사용해서 풀 수 있었다. 우선 우선순위 큐를 사용해서 간선의 가중치를 비교해서 작은 간선부터 선택하도록 했다. 간선을 선택한 후에 양 끝 점들을 find를 통해서 root를 찾고 root가 서로 다를 경우 cycle을 생성하지 않으므로 두 root를 union하고, 만약 같다면 cycle을 생성하므로 넘어간다. union을 했다면 간선을 추가한 것이기 때문에 result에 간선의 weight를 더해준다. 모든 간선에 대해서 반복 실행하고 result를 출력해서 해결 할 수 있다.

코드일부

for(int i = 0; i < e; i++) {
		Edge edge = queue.poll();
			
		int start = find(edge.start);
		int end = find(edge.end);
			
		if(start != end) {
			union(start, end);
			result += edge.weight;
		}
		else {
			continue;
		}
	}