룰루랄라 알고리즘

N개의 정점을 2개의 집합으로 나눌 수 있는 모든 경우의 수에서 연결 요소가 2개인 그래프 찾기 삼성 sw기출문제 왤케 어렵냐 제한 시간이 매우 짧아서 시간초과를 걱정했는데 다행이 빠르게 되네 이게 왜 시간이 빠르지 아마도 값이 작아서 일 듯하다 코드가 내 기준으로 되게 더럽다. 좀 더 간결하고 예쁘게 줄이고 싶은데 푼 걸로 만족하자 bfs를 두번 돌리는게 매우 마음에 들지않는다. 최근 들어 조합, 순열 문제가 꽤 많은 듯 아직 bfs의 개념이 완벽하진 않은것 같다. 문제풀이는 너무 복잡해서 주석으로 대체 했다.

그래프를 따라 번갈아가면서 색을 칠하다가 이미 방문했던 정점이 이전 정점 색과 같은 색이라면 이분그래프가 아니다. 색은 dfs 함수에서 group과 -group을 번갈아 넘겨주면서 1과 -1로 표현한다. result를 True로 선언 하고 dfs 함수에서 만약 정점의 색이 같다면 False를 리턴해 result에 저장 마지막에 result의 값에 따라 이분그래프 판별 출력 *주의* 재귀 함수 dfs에서 return을 했을 때 현재 돌고있는 함수만 종료 된것이지 dfs함수 전체가 종료되는 것이 아니다. return False를 하더라도 종료되는 것은 dfs의 전체 과정이 아니라 딱 현재 실행되고 있는 함수뿐이다. 처음에 전역에서 호출된 dfs와 그 dfs가 호출한 dfs는 서로 다른 함수이며, 그 dfs가..