yhjin210   3년 전

알고리즘 구현을 다음과 같이 했습니다.

dfs 로 첫번째 구역 케이스 구하기 ( 1~ N/2)

이 때 연결되어 있을 경우에만 집어넣어서 케이스를 확인했습니다.

그래프 연결이 3<->4<->1 일때 1 3 4랑 1 4 3 모두 탐색을 해줘야되는 것 같아서 이렇게 짯습니다.

그 다음에 각 케이스에 대해 나머지 방문하지 않은 노드들에 대해 ( 두번째 구역 후보)

방문하지 않은 노드 하나에서 bfs를 했을 때 유효함은 모든 노드가 방문되어야된다고 생각했고

각 과정에서 두 구역의 인구합을 구했습니다. (res_a, res_b)

관련 질문 중에

8
17 42 46 81 71 8 37 12
4 2 4 5 7
5 1 3 4 5 8
2 2 4
5 1 2 3 7 8
5 1 2 6 7 8
2 5 8
4 1 4 5 8
5 2 4 5 6 7

이 답이 2가 나와야 한다고 그러는데

2 4 8 / 1 3 5 6 7 케이스에서 2 차이가 나는 것을 확인했습니다.

그런데 3번 노드가 2번, 4번과 연결되어 있어서 (1 구역) 2 구역에서는 연결되지 않았기 때문에 두 구역으로 나눌 수 없는 케이스가 되지않나요?


혹은 구역이 다르게 나뉘는 건지 ; 논리가 어디가 잘 못 된건지 지적부탁드립니다. 

아무 답변이나 감사합니다.

yhjin210   3년 전

자답) dfs를 하는게 아니라

첫번째 구역에 대한 nCr 조합 셋을 구해서 bfs 두개를 돌리는게 맞는 답이군요 :D

wkd6576   2년 전

위에서 말씀해주신

8
17 42 46 81 71 8 37 12
4 2 4 5 7
5 1 3 4 5 8
2 2 4
5 1 2 3 7 8
5 1 2 6 7 8
2 5 8
4 1 4 5 8
5 2 4 5 6 7

이 답이 2가 나와야 한다고 그러는데

2 4 8 / 1 3 5 6 7 케이스에서 2 차이가 나는 것을 확인했습니다.

그런데 3번 노드가 2번, 4번과 연결되어 있어서 (1 구역) 2 구역에서는 연결되지 않았기 때문에 두 구역으로 나눌 수 없는 케이스가 되지않나요?

이 부분이 저도 이해가 가지 않는데.... 어떻게 해결하신건지 여쭤봐도 될까요...? 2 4 8 / 1 3 5 6 7 애초에 이렇게 나뉠 수가 없는거 아닌가요?? 이렇게 되면 3번이 고립되어서 아예 두 개로 나눌 수 없는 경우라고 생각했는데 이게 아닌건가요?

댓글을 작성하려면 로그인해야 합니다.