[LeetCode] 785. Is Graph Bipartite?

📌 문제 요약 및 핵심 아이디어

• 문제 목표: 주어진 무방향 그래프가 이분 그래프(Bipartite Graph)인지 판별하기
• 풀이 핵심:
  • 연결된 두 노드는 서로 다른 그룹(A팀 / B팀)에 속해야 함.
  • 한 노드를 특정 팀으로 지정했다면, 이웃한 모든 노드는 무조건 반대 팀으로 칠하며 확장해 나가야 함.
  • 탐색 도중 이미 팀이 정해진 이웃 노드가 같은 팀으로 칠해져 있다면 이분 그래프가 불가능(false).

💡 접근 방식 및 시행착오

1. 첫 번째 시도 (Wrong Answer)

• 단순 for문으로 0번 노드부터 순차적으로 이웃 노드의 팀을 정해주는 방식 작성.
• 문제점:
  1. 비연결 그래프 처리 불가: 그래프가 여러 조각으로 쪼개져 있거나 고립된 노드가 있으면 탐색이 누락됨.
  2. BFS/DFS 탐색 부재: 연결된 노드들을 연속적으로 방문하는 탐색 구조가 아니어서 팀 배정이 꼬임.

2. 정답 접근 (BFS 가이드)

1. 상태 관리: 각 노드의 방문 여부 및 팀 상태를 나타낼 team 배열 생성 (null: 미방문, 'A' / 'B': 배정 완료).
2. 외곽 for문 순회: 그래프가 여러 개로 쪼개진 비연결 그래프(Disconnected Graph)일 수 있으므로, 아직 팀이 배정되지 않은(null) 노드를 만날 때마다 새로운 출발점으로 삼아 BFS 탐색 시작.
3. BFS 탐색 수행:
   • 현재 노드의 인접 노드(neighbors)를 하나씩 확인.
   • 인접 노드가 아직 팀이 없다면: 현재 노드의 반대 팀을 배정하고 큐(Queue)에 삽입.
   • 인접 노드가 이미 팀이 있다면: 현재 노드와 같은 팀인지 확인. 같은 팀이라면 조건 위반이므로 즉시 false 반환.

🛠️ 최종 코드 (TypeScript)

function isBipartite(graph: number[][]): boolean {
    const n = graph.length;
    // null: 미방문, 'A'|'B': 팀 배정 완료
    const team: ('A' | 'B' | null)[] = Array(n).fill(null);

    for (let i = 0; i < n; i++) {
        // 이미 팀이 정해진 노드는 스킵 (이전 연결 요소 탐색 시 처리됨)
        if (team[i] !== null) continue;

        // 새로운 연결 요소(Component) 탐색 시작
        team[i] = 'A';
        const queue: number[] = [i];

        while (queue.length > 0) {
            const curr = queue.shift()!;
            const neighbors = graph[curr];

            for (const neighbor of neighbors) {
                // 1. 인접한 노드가 나와 같은 팀이라면 이분 그래프 불가능
                if (team[curr] === team[neighbor]) return false;

                // 2. 인접한 노드가 아직 팀이 없다면 반대 팀 지정 후 큐에 추가
                if (team[neighbor] === null) {
                    team[neighbor] = team[curr] === 'A' ? 'B' : 'A';
                    queue.push(neighbor);
                }
            }
        }
    }

    return true;
};