백준 #1707번 #이분그래프 #그래프알고리즘 #알고리즘 #그래프 #bfs #파이썬 #python

[백준] 이분 그래프 (1707번) - Python / 알고리즘

✅문제 - 이분 그래프 (1707번) ✅필요 알고리즘 개념 - BFS🔵 BFS 활용 방법◼ 이 문제는 연결된 두 Node를 다른 색으로 색칠하는 것이 가능한지 물어보는 문제이다. 예를 들어 아래 처럼 인접한 두 노드를 서로 다른 색으로 칠할 수 있다면 이분 그래프로 나눌 수 있는 그래프이다. 하지만 아래의 경우 Node 5번을 보면 빨간 Node와 파란 Node와 모두 연결돼 있기 때문에 인접한 Node와 다른 색으로 칠할 수 없다. 그러므로 이분 그래프가 아니다.이 아이디어를 활용하여 BFS를 구현하면 이분 그래프를 확인할 수 있다.✅코드 설명 - BFS 구현 부분def bfs(graphs,visited): queue = deque() # graphs 는 edge를 입력 받은 list이다 ..