- Quiz
- Test Cases
- Solution
- Solution 1
- Solution 2
두엣지연결 그래프
Unweighted, Undirected 그래프를 나타내는 edges 배열이 제공되면, 주어진 그래프가 두엣지연결 그래프인지 여부를 판단하는 함수를 작성합니다.
그래프의 모든 vertex의 쌍에는 각 vertex를 연결하는 하나 이상의 edge가 존재합니다. 연결되지 않은 그래프는 연결이 끊어진 것으로 합니다.
두엣지연결 그래프는 그래프에 있는 아무 edge 한 개를 제거했을 때, 그래프 연결이 끊어지지 않는 경우의 그래프 입니다. 한개의 edge를 제거했을 때, 그래프가 분리되면 두엣지연결 그래프가 아닙니다. 만약 주어진 그래프가 이미 끊어진 경우에도 그 그래프는 두엣지연결 그래프가 아닙니다. 비어 있는 그래프는 두엣지연결 그래프로 간주됩니다.
Adjacency 리스트라고 하는 입력배열이 그래프를 나타냅니다. 그래프의 vertex 수는 입력 받은 edge배열의 길이와 동일합니다. edge배열의 인덱스가 바로 vertex 입니다. edge 방향이 없이 양 방향으로 이동이 가능합니다. vertex i와 vertex j가 연결된 경우 i -> j, j -> i로 양방향 이동이 가능합니다. 예를 들어 두개의 vertex와 한개의 edge가 있는 방향성 없는 그래프는 edges = [[1], [0]]으로 표시됩니다.
주의: 그래프에는 중복 edge(동일한 출발점과 종착점을 공유하는 edge)가 포함되지 않습니다. 즉, 동일한 두 vertex를 연결하는 두 개의 edge가 존재하지 않습니다.
예제 1
입력
edges = [ [1, 2, 5], [0, 2], [0, 1, 3], [2, 4, 5], [3, 5], [0, 3, 4] ]
출력
true
Test Case 1
Input
edges = [
[1, 2, 5],
[0, 2],
[0, 1, 3],
[2, 4, 5],
[3, 5],
[0, 3, 4]
]
Output
true
Test Case 2
Input
edges = [
[1, 2, 5],
[0, 2],
[0, 1],
[4, 5],
[3, 5],
[0, 3, 4]
]
Output
false
Test Case 3
Input
edges = [
[1, 5, 7],
[0, 2],
[1, 3, 6],
[2],
[5, 6],
[0, 4, 6],
[2, 4, 7],
[0, 6]
]
Output
false
Test Case 4
Input
edges = [
[1, 5, 7],
[0, 2],
[1, 3, 6],
[2, 4],
[3, 5, 6],
[0, 4, 6],
[2, 4, 7],
[0, 6]
]
Output
true
Test Case 5
Input
edges = []
Output
true
- My Answer
- Lecture
- Output
프로그래밍을 이해하는데 꼭 필요한 알고리즘을 쉽고 빠르게 배울 수 있도록 준비한 강의 입니다.
코딩테스트를 준비하시는 분, 알고리즘에 대해서 전반적으로 공부하고자 하는 분들을 위해 꼭 필요한 토픽을 모아서 기초부터 고급 문제까지 단계적으로 구성되어 있습니다.
프로그래밍 언어는 JavaScript · Java · Python · C++ · C# 을 이용하여 브라우저에서 직접 프로그램을 작성 및 실행할 수 있으며, 알고리즘 강의를 통해 주어진 문제를 응용하여 다양한 솔루션을 작성하고 온라인에서 바로 테스트하면서, 알고리즘에 대해 좀 더 깊은 이해를 도와 드립니다.
코딩테스트 문제해설
온라인으로 코딩문제 풀면서 학습하는 사이트를 찾고 계신가요? W+코딩에서는 코딩공부 하면서 헷갈리는 부분을 알기 쉽고 정확하게 알려드립니다.
알고리즘 코드해설
바이너리트리, 링드리스트, 그래프, 다이나믹 프로그래밍, 그리디 등등등... JavaScript, Java, Python, C++, C# 솔루션을 정확하고 알기 쉽게 설명해 드립니다.