Python_수업 (7)

오늘 할 일

그래프 이론

---

1. 구현 ex. 사칙연산 빠르게 구하기
2. 기타(자료구조론)
3. 그래프 이론

그래프 이론

1. 관련 용어 숙지하기
   • 정점(노드, Vertex)과 간선(Edge), 가중치
   • 유향(일방향) 그래프와 무향(양방향) 그래프 ex. SNS 친구 관계 ㅋㅋㅋ
   • 희소 그래프와 밀집 그래프, 완전 그래프 → 시간 복잡도 때문에 사용 but 중요하진 않지만 완전 그래프는 약간 중요함 ㅋㅋㅋ
   • ex. 외판원 문제 → 완전 그래프
   • 스택과 큐 복습!
     • 큐
       • 선입선출
       • 나가는 건 처음 들어간 것 들어올땐 마지막으로
       • 시간 복잡도상 리스트 구현 힘들다. (pop(0) → O(N) / append() → O(1)) → deque
       • deque
         • 자료의 선입과 선출이 중간에 이뤄지지 않고 양 끝에서 이뤄진다.

       from collections import deque
       
       queue = deque()
       queue.append(5)
       queue.append(6)
       queue.append(3)
       print(queue)      # deque([5, 6, 3])
       a = queue.popleft()
       print(a)          # 5
       
       ---------------------------------------------
       
       from collections import deque
       
       queue = deque([5, 6, 3])
       print(queue)      # deque([5, 6, 3])
       

     • 스택
       • ex. 뒤로가기
       • 오른쪽으로 들어가고 나중에 들어간 원소가 먼저 나간다.
       • 시간 복잡도상 리스트로 구현해도 괜찮다(append() → O(1) / pop() → O(1))
2. 그래프 구조화(인접행렬 vs 인접리스트) ← 이차원 리스트 형태로 구조화!
   • [문제] BOJ 2606 바이러스
     • 인접 행렬 → 행에서 출발, 열에서 도착 (직접적인 연결)
     • 인접 리스트 → 정점의 번호를 리스트에 적는다. 그걸 커다란 리스트로 닫는다.
     • 인접 행렬 & 인접 리스트 만들기
       1. 빈 판 만들기(정점의 개수, V)
       2. 간선 정보 입력하기(간선의 개수, E)
       3. (가중치 표현)

     '''# 인접 행렬'''
     from pprint import pprint
     
     V = int(input())
     E = int(input())
     
     # 빈 판 만들기
     com = [[0] * (V+1) for _ in range(V+1)]
     
     # 간선정보 입력받기
     for _ in range(E):
         N, M = map(int, input().split())
         com[N][M] += 1
         com[M][N] += 1
     
         # 가중치
         # N, M, w = map(int, input().split())
         # com[N][M] += w
         # com[M][N] += w
     
     pprint(com)
     
     # [[0, 0, 0, 0, 0, 0, 0, 0], 
     #  [0, 0, 1, 0, 0, 1, 0, 0], 
     #  [0, 1, 0, 1, 0, 1, 0, 0], 
     #  [0, 0, 1, 0, 0, 0, 0, 0], 
     #  [0, 0, 0, 0, 0, 0, 0, 1], 
     #  [0, 1, 1, 0, 0, 0, 1, 0], 
     #  [0, 0, 0, 0, 0, 1, 0, 0], 
     #  [0, 0, 0, 0, 1, 0, 0, 0]]
     

     '''인접 리스트'''
     from pprint import pprint
     
     V = int(input())
     E = int(input())
     
     # 빈 판 만들기
     adj = [[] for _ in range(V+1)]
     
     # 간선정보 입력받기
     for _ in range(E):
         s, e = map(int, input().split())
         adj[s].append(e)
         adj[e].append(s)
     
         # 가중치
         # s, e, w = map(int, input().split())
         # adj[s].append((e, w))
         # adj[e].append((s, w))
     
     pprint(adj)
     
     # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
     

   • 장단점
     • 인접 리스트 : 탐색이 빠르다!
     • 인접 행렬 : 방향 전환이 쉽다! → 전치
   • 다음 시간이지만..New 2차원 리스트 → 인접 행렬, 인접 리스트와 완전 다른 내용!!!
     • 그래프 → 입력받아서 그대로 사용하면 된다.
       • 일반적인
       • 2차원 리스트
       • [문제] 7576 토마토
3. 그래프 탐색(DFS vs BFS)
   • 목적 : (특정한 규칙을 가지고) 중복 없이 모든 정점을 방문하는 것
   • 규칙
   • DFS (깊이 우선 탐색) → 방문과 탐색의 연속 (탐색 즉시 방문)
     1. 정점을 방문합니다.
     2. 방문했다고 표시합니다. → 중복 X
     3. 해당 정점에서 방문할 수 있는 정점이 있다면 바로 방문합니다.
     4. 없다면 되돌아갑니다.
     • 스택
     • 재귀
   • BFS (너비 우선 탐색) → 탐색 후 방문 (최단 거리 알고리즘)
     1. 정점을 방문합니다.
     2. 방문했다고 표시합니다.
     3. 해당 정점에서 방문할 수 있는 정점을 모두 탐색합니다.
     4. 현재까지 탐색된 정점들 가운데 가장 먼저 탐색된 정점을 방문합니다.
     • 큐
   • 장단점
     • 완전탐색 - 무방
     • 경로의 특징 - DFS
     • 최단거리 - BFS