실행시켜보면서, 87-88사이에 r,c,mr,mc를 찍어보면 쉽게 알 수 있습니다.
1 5 10 4 7 4 4 4 4 6 4 4 7
이 예시의 경우, [0][0]-[0][4], [0][2]-[0][3], [1][0]-[1][1], [1][2]-[1][3]으로 묶일 수 있고 그래서 정답이 6이 나옵니다.
질문자 분의 코드에 의하면, 처음에 [0][0]을 찾고, 이후 [1][0]와 [0][4]에 대해 동일하게 가장 차수가 낮은 노드 조건을 만족합니다. 이런 "중복되는 선택 조건"이 발생하는 경우 해당 방식은 항상 최선을 보장하지 못하게 됩니다.
질문자분의 코드에서는 아래와 같이 매칭이 발생하기 때문에 틀렸습니다.
[0][0]-[1][0] [0][4]-[0][3] [1][1]-[1][2]

zome0103 10달 전
한부대로 두영역을 커버가능할 경우 간선이 있다고 정의했습니다.
진입차수가 낮은 노드부터 순회하면서 주변노드중 진입차수가 가장 낮은 노드와 매칭 시켰습니다.
매칭된 노드의 주변에 있는 노드는 진입차수를 업데이트 한 후 다시 우선순위큐에 넣어줬습니다.
카운트 방식은 매칭할 때마다 최대 부대수에서 1씩 빼주면서 카운트 했습니다.
다음은 반례입니다.
정답: 6
출력: 7
도움 부탁드립니다 ㅜㅜ