[Python] 이것이 코딩테스트다 10장 그래프 이론

그래프 이론의 핵심

 

지금까지 배운 내용

 

 

• 시간 제한 참고

파이썬 => 1초 20000000번 연산

 

데이터 20,000,000 => O(N)

데이터 1,000,000 => O(NlogN)

데이터 4~5,000 => O(N^2)

데이터 100~200 => O(N^3)

 

 

 

• 그래프의 구현 방법

노드의 개수가 V, 간선의 개수가 E라고 하면

 

인접 행렬 : 2차원 배열을 사용하는 방식

인접 행렬의 경우 O(v^2) 만큼의 메모리 공간 필요 (메모리 측면) 

인접 행렬의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(1)의 비용이 듦 (속도 측면)

 

인접 리스트 : 리스트를 사용하는 방식

인접 리스트의 경우 O(E) 만큼의 메모리 공간 필요 (메모리 측면) 

인접 리스트의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(V)만큼의 시간이 든다. (속도 측면)

 

 

 

서로소 집합

 

핵심 : Parent 배열을 생성하여  재귀 함수로 부모노드를 찾는다. 

만약 부모노드가 같으면 서로소가 아니라 같은 집합에 있는 노드.

 

union_parent , find _ parent 함수 구현하면 반은 완성

대략 O(nlogn)

 

사이클 판별: union 실행하기 전에 이미 루트노트가 같다면 사이클 발생

 

 

 

 

크루스칼 알고리즘

 

최소비용 신장트리 만드는 알고리즘 O(eloge)

원리: 사이클이 발생하지 않는 한, 간선의 최소부터 집합에 포함한다. 따라서, 간선은 정렬해 놓기

 

 

 

위상 정렬

 

큐와 리스트를 이용하여, 노드를 정렬하는 방식  ( 답은 한가지가 아니라 여러가지가 될 수 있음)

BFS를 이용한다고 봐도 무방할 정도로 매우 비슷함 O(v+e)

 

 

---

서로소 예제

 

 

🎨 서로소 사이클 판별

 

 

 

🔑 Key Point 

 

사이클 판별: union 실행하기 전에 이미 루트노트가 같다면 사이클 발생

 

---

크루스칼 예제

 

 

 

🎨 크루스칼 코드

 

 

 

 

 

 

🔑 Key Point 

 

간선을 우선 입력받아 리스트에 넣은 뒤, 간선의 비용을 기준으로 정렬한다. 

그리고 적은 간선의 비용 순서대로  union하기 전에 사이클이 발생하는지 확인하고, 발생 안한다면 집합에 넣는다.

 

 

 

---

위상정렬 예제

 

🎨 위상정렬 코드

 

 

 

 

 

🔑 Key Point 

 

BFS랑 매우 비슷하다. 그 순서대로 그냥 노드 넣으면 정렬 끝

 

---

팀 결성

시간제한 2초 . 데이터 10,000개 

 

 

 

 

📝 체감 난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드 

 

 

 

🔑 Key Point 

 

같은 팀인지 아닌지 , 즉 서로소인지 아닌지 판별하는 문제 

 

---

도시 분할 계획

시간제한 2초 . V = 100000 E = 1000000

 

 

체감 난이도 : ★★☆☆☆

 

🎨 내가 짠 코드

 

 

 

🔑 Key Point 

 

최소비용 신장트리를 장황하게 설명해놓은 문제 ! 그중에서 가장 큰 노선을 없애면 됨.

간선의 개수가 딱 O(eloge)의 시간복잡도를 허용하는 커트라인.

 

---

커리 큘럼

시간제한 2초

 

 

 

체감 난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

🔑 Key Point 

 

for i in range(1,n+1):
    line = list(map(int, input().split()))
    time[i] = line[0]
    for x in line[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

-1 이 나올때 까지 입력받기 처리!

파이썬 부록 살펴 볼 것

 

 

---

마무리

 

서로소 구하는 집합 알아두면 크루스칼 , 사이클, 위상정렬 구하기 쉬워진다