[BOJ] 백준 1707 이분 그래프 (Swift)

문제

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

풀이

먼저, 이분 그래프에 대해 알아야 풀 수 있습니다.
이분 그래프는 나와 인접한 노드는 다른 집합이여야 합니다.

구글링해서 이해하기 쉬웠던 방법은 나와 인접한 노드는 다른 색깔을 칠해주어야 한다. 라고 이해하였습니다.

그렇다면 DFS 혹은 BFS로 탐색하면서, 방문할 때 색을 칠해주는 방법으로 구현해야겠다고 생각했습니다.

인접 노드가 방문하지 않은 노드라면 나와 다른 색을 칠해주었습니다.
인접 노드가 방문한 노드인데 나와 같은 색으로 칠해져있다면 이분 그래프가 될 수 없습니다.

소스코드

후기

문제를 풀 때, 이분 그래프가 정확하게 뭔지 몰라서 이분 그래프에 대해 찾아보고 풀이했습니다.
이분 그래프에 대해 이해했다면, BFS 혹은 DFS를 조금 응용하면 풀 수 있는 문제였습니다.