snorlaxious   4년 전

문제의 테스트케이스와 질문 검색에서 찾은 테스트케이스들을 모두 확인했는데 문제가 없었어서 질문 남깁니다.

N이 작아서 시간 초과가 날 가능성도 적을 것 같았고 시간 초과가 났을 경우 해결하자는 생각으로 가지치기는 하지 않은 상태입니다.

우선 제 생각은, 선거구를 A와 B그룹으로 나누기 위해(district[idx] == 0일 경우 A그룹, 1일 경우 B그룹으로 두었습니다.)

모든 노드를 B그룹으로 초기화시킨 다음, 한 노드를 정해 해당 노드를 A그룹으로 바꾸고 인접한 노드를 A그룹으로 바꿔가면서

각 단계마다 두 그룹 간의 인구 수 차이를 비교해 MIN을 갱신하는 방식입니다.

두 그룹으로 나뉘어지지 않을 경우의 체크는, 각 그룹에 속한 한 노드를 선택 후 dfs를 통해 인접 노드로 퍼져가면서

각 그룹에 속하는 노드의 갯수를 확인하여, 한 그룹이 0개이거나 두 그룹의 합이 N개가 되지 않을 경우

두 그룹으로 정상적으로 나눌 수 없다고 판단하여 return하는 방식입니다.


시작점 노드를 1~N번까지의 루프를 돌면서 고르는데, 이 때마다 그룹의 상태를 모두 B그룹으로 초기화시키기 때문에

루프마다 중복 케이스는 존재하겠지만 빠지는 케이스는 없다고 생각하고 짠 코드인데 무엇이 문제인지 잘 모르겠네요...

danimartinwife   4년 전

우선 전체적인 로직도 정답으로 처리된 제 코드랑 같구요, 구역까지는 잘 나누셨으니까 연결 요소 확인하는 bfs/dfs를 각 구역당 시작점부터 한번만 진행하시고, 한 구역 bfs/dfs 돌고 난 후 visit이 하나라도 되지 않았으면 연결이 되지 않았다고 판단하니 정답 처리되었습니다. 제가 달아드린 주석 참고해주세요. 문제에 따라서 for문으로 각 정점마다 dfs를 여러번 돌릴지, dfs 한번만 돌리고 연결요소 판단하는지 다른거 같습니다.

snorlaxious   4년 전

답변 감사드립니다.

답변을 읽고 아무리 생각해봐도 말씀하신 방법과 제 방법에 차이점이 없는 것 같아서

선거구를 나누는 부분에 문제가 있는 것이 아닌지 판단되어

기존의 선거구를 나누는 부분이었던 search 함수 부분을 아래 코드와 같이 바꾸어주니 해결되었습니다.


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