Vertex와 directed edge를 사용해서 graph를 구현하는 방법을 알아야 풀 수 있는 문제입니다.
- class Vertex와 Edge를 사용해서 graph를 구현할 수 있구요.
- Vertex으로 들어오는 edge가 incoming edge
- Vertext에서 다른 Vertex로 나가는 edge가 outgoing edge 입니다.
이제, graph를 코드로 표현할 수 있게 되었구요,
문제에서 말하는 아래 문장을 잘 이해해야 문제를 풀 수 있습니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.
첫번째로 해야할 일은 임의의 정점을 우선 찾아야 합니다.
문제입력으로는 edge만 주어지고, 정점이 주어지지 않습니다.
정점의 특징이 있는대요
- incoming edge가 없다는 것이죠.
이것 만으로는 정점을 특정할 수 있습니다.
정점을 찾았으니, sub graph가 그래프가 도넛, 막대기, 8자, 그래프 중에 어떤 종류의 그래프인지 판단하는 로직이 필요합니다.
정점에서 outgoing 에지를 하나 선택하고, 에지의 to 에 해당하는 vertex를 선택합니다.
이번 풀이에서는 DFS 방식으로 edge를 탐색하겠습니다.
- 도넛 subgraph를 DFS로 계속 탐색해보면, 어떤 vertex에서 시작하던지, 방문했던 vertex로 되돌아 오게 됩니다. 따라서, visited vetex를 다시 방문했다면, subgraph가 도넛 모양인 것을 알 수 있습니다.
- 막대 subgraph incoming edge만 있고, outgoing edge가 없는 vertex가 반드시 있음
- 8자 subgraph는 visited vertex를 만나기 전에, incoming edge가 2개, outgoing edge가 2개인 vertex를 travel 하게 됩니다.
댓글 없음:
댓글 쓰기