리트코드를 풀어보면서 solution을 혼자 생각해서 풀어보려고 노력했으나, 쉽지 않은걸 깨닫고 이제는 오래전 구매해두었던 “알고리즘 트레이닝”이라는 책과 함께 공부하면서 풀어보려고 합니다.
207번 문제는 그래프에 관한 문제입니다.
https://leetcode.com/problems/course-schedule/
그래프의 기본 용어부터 알아봅니다.
- 그래프 : 노드와 그들을 잇는 간선으로 구성
- 경로 : 한 노드에서 그래프의 간선을 지나 다른 노드로 가는 길
- 연결 그래프 : 모든 노드간에 경로가 있는 경우 연결 그래프라고 부름
- 컴포넌트 : 그래프의 연결된 부분( 전체 그래프 내에서도 연결된 노드의 그룹)
- 트리 : 사이클이 없는 연결 그래프
- 차수(Degree) : 이웃 노드의 개수
- 정규 그래프 : 모든 노드의 차수가 같은 그래프
- 진입차수(Indegree) : 그 노드로 향하는 간선의 개수
- 진출차수(Outdegree) : 그 노드에서 시작하는 간선의 개수
- 이분 그래프 : 색깔을 2개로 칠하되, 이웃 노드의 색깔이 같은 경우가 없는 그래프
그래프를 표현사는 방법은 다양하지만 3가지 방법이 대표적입니다.
- 인접 리스트
Node의 길이만큼 array 를 생성하여 각 노드의 간선을 array 의 index 로 관리하는 방법
가장 대중적인 방법 - 인접 행렬(adjacency matrix)
2차원 배열로 행렬의 값들은 각 노드간 간선 혹은 가중치를 나타냄
n^2의 array를 관리해야하고 대부분이 0으로 채워지며, 그래프가 크면 사용하기 어려움
- 간선 리스트
그래프의 모든 간선을 특정 순서에 따라 저장한 리스트
set이나, array 처럼 0번째, 1번째 index를 사용하여 간선을 표현
그래프를 표현하는 방법을 체계적으로 알기전에는 간선 리스트를 사용하여 표현하려고 노력했으나, 인접 리스트를 사용하는게 코드가 깔끔하고 직관적이여서 더 좋은것 같습니다.
207번 문제도 인접 리스트로 표현해서 문제를 풀어봅니다.
그래프를 탐색하는 방법은 2가지가 있습니다.(DFS, BFS)
DFS 는 직관적인 탐색방법으로 재귀식을 사용하여 구현합니다.(stack도 Ok)
BFS 는 queue를 사용하는 방법입니다.
두 방법의 시간 복잡도는 O(n+m) , n:노드 개수, m:간선 개수 로 동일합니다.
그래프를 탐색하면서 그래프의 연결성, 사이클 존재 여부, 이분성(이분 그래프 여부) 를 확인할 수 있습니다.
책(“알고리즘 트레이닝”)에서 그래프에서 최단 경로 구하는 방법을 3가지 소개하고 있는데요.
( 벨만-포드 알고리즘 / 다익스트라 알고리즘 / 플로이드-워셜 알고리즘 )
자세한 설명은 그래프의 최단 경로를 구하는 문제를 풀때 공부해보려고 합니다.
207번 문제는 그래프의 사이클이 있는지를 확인하는 문제입니다.
저는 우선 위상정렬 알고리즘을 사용하여 문제를 풀었습니다.
(위상정렬 : 노드 a->b 로 가는 경우가 있는 경우 노드 a 가 b 보다 먼저 나오도록 하는 정렬 )
그래프의 위상정렬을 위해서는 노드를 3가지 상태로 관리합니다.
- 0번 상태 : 노드가 아직 처리되지 않음(초기화)
- 1번 상태 : 노드가 처리되는 중(노드의 탐색을 시작했고 아직 하위 노드를 탐색 중)
- 2번 상태 : 하위 노드의 탐색을 포함 노드의 처리가 종료됨
노드의 1번 상태가 하위 노드의 탐색 여부와 관련 있기 때문에 DFS 로 그래프를 탐색해야합니다.
DFS 탐색 중 노드의 상태가 1인 노드를 다시 방문 할 경우 사이클이 존재하는 그래프입니다.
노드의 상태가 2가 되었을때 array 에 넣고 탐색이 종료되었을때 그 array를 reverse 하면 위상 정렬을 완성할 수 있습니다.
207번 문제를 풀었던 순서입니다.
- 노드의 상태값 초기화
- 입력값을 인접 리스트로 표현
- DFS 탐색
https://github.com/sok891111/leetcode/blob/main/.26/207.%20Course%20Schedule.py
책에서는 더 좋은 알고리즘으로 “플로이드 알고리즘” 으로 사이클을 찾는 방법을 소개합니다.
2개의 pointer를 사용하여 a는 한번씩 이동하고 b는 2번씩 이동시켜 서로 다른 속도의 포인터가 만난다면 사이클이 존재하고 아니라면 존재하지 않는 알고리즘입니다.
Floyd’s cycle finding algorithm 를 사용해서 207번 문제를 푸는건 Next level 문제로 남겨두겠습니다.