0은 아무 색도 칠해져 있지 않은 상태, 1은 검은색, 2는 빨간색이라고 생각합시다.
[34라인] 색이 없는 정점을 발견하면 DFS를 시작하므로 모든 정점에 색깔을 칠하게 될겁니다. 이쪽을 한 번도 방문하지 않았다는 것은 이쪽 컴포넌트는 아직 방문 한 적이 없다는 것(이분 그래프라는 가정하에)이니 아무 색으로나 칠해도 무방합니다. 따라서 그냥 1부터 칠합시다.
[9라인] DFS를 이용해 현재 정점과 인접한 정점들에, 현재 정점의 색과 다른색으로 칠해줍니다. 여기서 현재 색이 C라면 3-C가 다른색을 의미하게 됩니다. (1이면 2, 2면 1)
[40라인] 이제 모든 정점을 색칠했으므로 확인해봅시다. 만약 이분 그래프라면 위의 과정대로 칠 했을 때 인접한 정점이라면 반드시 색이 달라야합니다. 만약 같은 것이 하나라도 있다면, 이분 그래프가 아닐것이 분명합니다.
swdream 5년 전
안녕하세요,
해당 내용 해답 코드를 보고 이해중인데, 도저히 이해 안가는 부분이 있어 죄송스럽게도 질문글 올립니다.
또한 dfs의 변수로 node 값과 정수 c값을 받는데,
이 c 값의 의미를 이해하기가 힘드네요.
color라는 배열에다가 node 값 순으로 ( color[node]이니..) c값을 처음에 할당주고,
그 이후에는 a[node]의 값들을 돌면서 next에다가 다음 node가 이어지는 정점의 값을 넣어주네요.
그리고, color라는 배열을 이용하여 next라는 정점이 방문하지 않은 경우면, 다시 dfs(next, 3-c)를 실행해준다는 의미구요.
여기서 dfs(next, 3-c)라는 함수 속의 함수가 잘 이해되지 않습니다. 그리고 3-c를 특별히 설정해주는 이유에 대해서도요..