1197 최소 스패닝 트리
크루스칼 알고리즘
프림 알고리즘
위와 같이 정점(V)이 4개, 간선(E)이 5개 있고 간선들을 가중치 기준 내림차순으로 정렬하였다.
첫 번째 간선을 골라 연결한다.
두 번째 간선을 골라 연결한다.
세 번째 간선을 골라 연결한다. 이 때 사이클(순환)이 발생하므로 세 번째 간선의 가중치는 추가하지 않는다.
네 번째 간선을 골라 연결한다. 이 때 모든 정점을 방문하였으므로 종료한다.
15683 감시
2637 장난감 조립
민제
우선순위는 '부품이 다른 부품의 재료로 쓰인 횟수'를 저장하여 사용하였다.
예제 입력 1을 그림으로 그려보면 다음과 같다.
우선 순위는 배열 cnt에 저장해두었고, 각 부품이 다른 부품의 재료로 쓰인 횟수를 저장하였다.
여기서 cnt 값이 0인 7번 부품을 먼저 계산한다.
7번 부품을 계산함에 따라 7번의 재료 부품인 4, 5, 6번 부품들의 cnt 값이 1씩 감소된다.
이어서 cnt 값이 0인 6번 부품을 계산한다.
6번 부품을 계산함에 따라 6번의 재료 부품인 3, 4, 5번 부품들의 cnt 값이 1씩 감소된다.
이어서 cnt 값이 0인 3번 부품을 계산한다.
3번 부품은 기본 부품이므로 다른 부품들의 cnt 값은 감소하지 않는다.
이어서 cnt 값이 0인 부품을 계산하는 과정을 반복하면
같은 부품을 여러 번 계산할 필요 없이 효율적으로 모든 부품의 개수를 구할 수 있다.
지훈
19238 스타트 택시
23818 원수의 원수
민제
root 배열에 {관계를 맺은 사람, 관계}를 저장해나가며 1번 예제를 푸는 과정은 다음과 같다.
먼저 기본적으로 각 노드는 자기 자신과 친구 관계이므로 위와 같이 기본값은 저장한다.
입력으로 1 1 2가 들어오면 2번 노드를 {1, 1}로 업데이트한다.
입력으로 1 2 3이 들어오면 3번 노드를 {2, 1}로 업데이트한다.
입력으로 0 3 4가 들어오면 4번 노드를 {3, 0}으로 업데이트한다.
입력으로 0 4 5가 들어오면 5번 노드를 {4, 0}으로 업데이트한다.
이어서 1과 3의 관계를 묻는다면 (1+1) mod 2 = 0, 친구이다.
마찬가지로 1과 5의 관계를 묻는다면 (1+1+0+0) mod 2 = 0, 친구이다.
하지만 위의 예제와는 다르게 한 사람은 여러 명과 관계를 갖고 있을 수 있다.
2번 예제를 푸는 과정은 다음과 같다.
입력으로 1 1 2가 들어오면 2번 노드를 {1, 1}로 업데이트한다.
입력으로 0 2 3이 들어오면 3번 노드를 {2, 0}으로 업데이트한다.
입력으로 0 1 3이 들어오면 문제가 발생한다.
다음주 과제
공부내용 및 소감