스위프트 코딩테스트 강좌, 이분 그래프 판별하기

이분 그래프란?
이분 그래프는 그래프의 정점 집합을 두 개의 상호 배타적인 부분 집합으로 나눌 수 있는 그래프입니다. 즉, 그래프의 모든 간선이 서로 다른 두 집합에 있는 정점 간에만 존재하도록 나누는 것입니다.
이분 그래프의 가장 일반적인 예는 ‘짝짓기’ 문제입니다. 예를 들어, 학생과 수업을 짝짓는 경우, 학생과 수업을 각각의 집합으로 입력하면 됩니다.
이분 그래프는 특히 2색 정점으로 항상 색칠이 가능하다는 성질을 가집니다.

문제 설명

주어진 무방향 그래프가 이분 그래프인지 판별하는 함수를 작성하십시오.
주어진 그래프는 인접 리스트 형태로 주어지며, 정점은 0번부터 n-1번까지의 번호로 연결되어 있습니다.
그래프가 이분 그래프인 경우 true 를 반환하고, 그렇지 않은 경우 false 를 반환해야 합니다.

입력 예시

    n = 4
    edges = [[0, 1], [0, 3], [1, 2], [2, 3]]

출력 예시

    false

문제 해결 과정

  1. 그래프의 구조 이해하기

    주어진 그래프는 노드와 간선으로 이루어져 있으며, 각각의 노드는 다른 노드와 연결되어 있습니다.
    그래프를 양방향으로 연결된 리스트 형태로 표현할 것입니다.
    자바와 스위프트를 포함한 많은 프로그래밍 언어에서 배열이나 해시맵을 사용하여 이 구조를 구현할 수 있습니다.

  2. 이분 그래프의 성질 및 탐색 방법

    이분 그래프는 정점을 두 개의 집합으로 나눌 수 있으며,
    모든 인접 정점이 서로 다른 집합에 속해야 합니다. 이런 성질을 활용하여 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 통해
    그래프를 색칠하는 접근 방식을 사용할 수 있습니다.

  3. DFS 또는 BFS를 사용하여 그래프 탐색하기

    그래프의 각 정점마다 색깔을 칠해가며 탐색을 시작합니다.
    색깔은 두 가지로 사용하며(예: 1과 -1), 이미 색깔이 칠해진 노드와 재방문하는 경우
    색깔이 일치하는 경우 이분 그래프가 아님을 알 수 있습니다.

코드 구현

이제 본격적으로 이분 그래프를 판별하는 알고리즘을 스위프트로 구현해보겠습니다.


    class Solution {
        func isBipartite(_ graph: [[Int]]) -> Bool {
            let n = graph.count
            var color = Array(repeating: -1, count: n) // -1은 색깔이 칠해지지 않음을 의미
            
            for i in 0..

예시 및 설명

위의 코드는 주어진 그래프를 순회하며 노드를 색칠하고 재방문 시 검사를 통해 이분 그래프 여부를 결정합니다.
위의 예시에서는 그래프가 다음과 같은 형태입니다:

    0 -- 1
    |    |
    3 -- 2

이 경우 0과 1 노드는 색깔이 다르고 1과 2 노드는 색깔이 다르며 2와 3 노드는 색깔이 다릅니다.
그러나 0과 3 노드는 동일한 색깔을 가지므로 이분 그래프가 아닙니다.
BFS 탐색을 통해 확인할 수 있습니다.

마무리

이 글에서는 이분 그래프에 대한 개념과 그 판별 과정을 설명하였으며,
스위프트로 이를 구현하는 방법을 알아보았습니다.
이 문제는 알고리즘 및 자료 구조의 기초를 다지는 데에 유용하며,
다양한 면접 질문에서 활용될 수 있습니다.
따라서 이 문제를 통해 이분 그래프와 색칠 알고리즘을 깊게 이해하는 것이 중요합니다.

참고 자료