[백준] 1707번:이분 그래프 (python 파이썬)

문제 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 처음엔 배열을 이용해 dfs를 사용하려 했는데, 메모리초과가 났다 ㅠㅠ 1과 2가 연결되어 있으면 arr[1][2] = arr[2][1] = 1 이런식으로 했더니 . . ! 방법을 바꿔서 bfs로 deque를 사용하여 해결했다. 이분그래프란, 간단히 말하면 인접한 정점끼리 다른 색으로 칠할 수 있는 그래프이다. 이를 visited 배열을 통해 방문하지 않았으면 0으로, 방문하였으면 -1과..
Coding - Algo/python 2021. 2. 24. 13:44
1