풀이
이분그래프에 대한 개념을 배웠으며 인접리스트를 활용한 BFS 역시 연습한 문제이다.
이분그래프란 인접하는 정점들이 서로 다른 그룹일 경우에 이분그래프라고 한다.
입력값이 각 간선정보를 주기 때문에 인접리스트 l 를 선언하여 각 정점마다 인접한 정점들을 리스트에 담아준다.
이후 그룹핑을 위한 group 리스트를 선언해준 뒤 BFS 를 실행한다.
시작점을 그룹1로 구분한 뒤 인접한 정점들 중 그룹핑이 되지않은 정점들에게 그룹-1로 구분해준다.
이를 반복하다가 만약 인접한 정점 중 현재 정점과 같은 그룹일 경우 이분그래프가 아니기 때문에 False 값을 반환한다.
이후 BFS 를 통해 반환받은 값을 통해 이분그래프 여부를 판단한 뒤 출력조건에 맞게 출력하면된다.
소스코드
References