1707
-
[백준] 1707번 이분 그래프 (by Python)Programming/Algorithm 2021. 2. 6. 00:39
문제 처음에 이분 그래프의 정확한 의미를 모르겠어서 조금 헤맸지만 결국 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프 라고 생각하면 될 것 같다. 이전의 연결 요소의 개수를 찾는 문제에서 BFS 방법보다 DFS 방법이 더 시간이 낮게 나오는 것을 확인하고 DFS로 들이댔지만 풀고 나니 BFS로 푸는 것이 더 나은 문제였다는 생각이 들어 BFS로도 풀어봤다. 그리고 DFS로 풀려면 sys.setrecursionlimit()을 일단 크게 줘야겠다는 교훈을 얻게 된 문제! 첫 번째 풀이 (by DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(100000) k = int(input(..