그래프 + BFS (게리맨더링)

N개의 정점을 2개의 집합으로 나눌 수 있는 모든 경우의 수에서 연결 요소가 2개인 그래프 찾기

삼성 sw기출문제 

왤케 어렵냐

제한 시간이 매우 짧아서 시간초과를 걱정했는데 다행이 빠르게 되네 이게 왜 시간이 빠르지 아마도 값이 작아서 일 듯하다

 

코드가 내 기준으로 되게 더럽다. 좀 더 간결하고 예쁘게 줄이고 싶은데 푼 걸로 만족하자

bfs를 두번 돌리는게 매우 마음에 들지않는다.

 

최근 들어 조합, 순열 문제가 꽤 많은 듯

아직 bfs의 개념이 완벽하진 않은것 같다.

 

문제풀이는 너무 복잡해서 주석으로 대체 했다.