궤도

문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으로 칠한 것을 볼 수 있을 것이다. 이분그래프는 인접한 두 정점을 다른색으로 칠한다고 가정할 때 오직 두가지의 색을 사용해서 모든 정점을 칠할 수 있는 그래프이다. 자료구조때 배웠던가...컴퓨터 알고리즘때 배웠던가...암튼 배웠었다. 아이디어는 간단한 이 문제가 정답 비율 20%대인 이유는 간과하기 쉬운 조건 하나와 메모리 초과 그리고 입력 초기화 떄문 아닐까싶다. 먼저 간과하기 쉬운 조건하나를 말해보도록 하겠다. 바로 모든 정점이 연결됐을거란 보장이 없다는 것이다. 이 그림처럼 다른 정점과 연결되지 않은 정점이 있을 수 있다..