두 팀으로 충돌 없이 나누기

자바스크립트 코딩테스트 문제로 bipartite-graph 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium bipartite-graph 함수명: solution 제한 시간: 300ms

문제 설명

n명의 참가자와 서로 같은 팀이 될 수 없는 관계 edges가 주어질 때, 모든 참가자를 두 팀으로 나누어 모든 충돌 관계가 서로 다른 팀 사이에만 놓이게 만들 수 있는지 반환하는 solution 함수를 작성하세요.

참가자 번호는 1부터 n까지입니다.

제한사항

1 <= n <= 10,000
0 <= edges.length <= 50,000
edges[i]는 [a, b] 형태이며, a번 참가자와 b번 참가자가 같은 팀이 될 수 없다는 뜻입니다.
같은 관계가 여러 번 주어질 수 있습니다.
a === b인 관계가 있으면 한 사람이 자기 자신과 다른 팀이어야 하므로 나눌 수 없습니다.
가능한 경우 true, 불가능한 경우 false를 반환하세요.

예시

입력: 4, [[1, 2], [2, 3], [3, 4]] → 출력: true
입력: 3, [[1, 2], [2, 3], [3, 1]] → 출력: false
입력: 6, [[1, 2], [2, 3], [4, 5]] → 출력: true
입력: 2, [[1, 1]] → 출력: false

힌트

참가자를 그래프의 정점, 충돌 관계를 간선으로 생각해 보세요.
한 참가자를 0번 팀으로 정했다면, 그 이웃은 반드시 1번 팀이어야 합니다.
그래프가 여러 덩어리로 나뉘어 있을 수 있으므로 아직 팀이 정해지지 않은 참가자마다 새 탐색을 시작해야 합니다.

해설

이 문제는 그래프가 이분 그래프인지 확인하는 전형적인 문제입니다.
BFS 또는 DFS로 정점을 방문하면서 현재 정점과 인접한 정점에 반대 색을 칠합니다.

탐색 중 이미 색이 칠해진 이웃을 만났는데 현재 정점과 같은 색이라면, 두 정점을 서로 다른 팀으로 보낼 방법이 없으므로 false입니다. 끝까지 모순이 없다면 모든 충돌 관계를 두 팀 사이로만 배치할 수 있으므로 true입니다.

주의할 점은 시작 정점 하나에서 닿는 사람만 확인하면 안 된다는 것입니다. 충돌 관계 그래프가 여러 연결 요소로 나뉘어 있을 수 있으므로 1번부터 n번까지 보며 아직 색이 없는 참가자를 만날 때마다 새 BFS를 시작해야 합니다. 또한 [1, 1]처럼 자기 자신과 충돌하는 관계는 색을 반대로 칠할 수 없기 때문에 즉시 실패입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과