알고리즘) 백준 1707번 이분그래프 Swift

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

1707번: 이분 그래프

---

예제

입력	출력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO
1 5 4 1 2 2 3 3 1 4 5	NO
1 5 4 1 2 3 4 4 5 3 5	NO
1 4 4 2 3 1 4 3 4 1 2	YES

 

---

문제 접근

문제에 이분 그래프에 대한 설명이 부족해서 쉽게 풀어 쓴 정의를 확인했습니다.

이분 그래프 : 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프

그래서 예제를 서로 다른 색을 한 번 칠해보았습니다.

• Case 1 : 1과 3이 다른색, 3과 2가 다른색이기 때문에 이분그래프가 맞습니다.
• Case 2 : 1과 2가 다른색, 2와 3이 다른색, 3과 4가 다른색이지만 2와 4가 같은 색을 띄어 이분그래프가 아닙니다.

예제를 그림으로 표현

인접한 노드를 모두 검사하여 처음 방문하면 반대 색을 칠하고, 이미 칠해져 있다면 비교합니다.
색을 새로 칠했다면 그 인접한 노드들도 모두 검사해봐야 하기 때문에 큐에 넣습니다.
간단한 듯 하지만 막상 구현하면 지저분하거나 시간초과, 메모리초과 등등 많은 시행착오를 겪었습니다.

보통 BFS 문제를 풀때 큐를 전역으로 선언하여 다 소진하면 결과를 출력했었습니다.
이분 그래프 문제는 노드별로 for문을 타고 그 안에서 큐를 활용해야 한다는 점이 접근하기 제일 어려운 포인트였습니다.

시간초과

• 개인적으로 함수를 구현하고 호출했을 때 시간 초과가 많이 난다고 느낍니다. 이 부분을 수정하면 시간초과 문제를 해결할 수도?
• 입력받을 때 Int를 String으로 감싼 뒤 받으면 시간이 절약됩니다; readLine()!.split(separator: " ").map { Int(String($0))! }
• for문 안에서도 result 값을 수시로 확인하여 탈출해야 시간초과 문제를 해결할 수 있었습니다.

메모리초과

• 인접한 노드를 표시할 때 [0...v+1][0...v+1]로 표현하니 메모리초과가 발생했습니다. links[2] = [3, 4] 과 같이 추가해줘야합니다.

 

풀이

---

참고

• https://blog.naver.com/gustn3964/222316562837
• https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html