Potato
μ•ˆλ…•ν•˜μ„Έμš”, κ°μž‘λ‹ˆλ‹€?πŸ₯” ^___^ 😺 github λ°”λ‘œκ°€κΈ° πŸ‘‰πŸ»

Algorithm/Basic

[μ•Œκ³ λ¦¬μ¦˜] ν”„λ‘œκ·Έλž˜λ°μ—μ„œ κ·Έλž˜ν”„λ₯Ό ν‘œν˜„ν•˜λŠ” 방식 (인접행렬 방식, μΈμ ‘λ¦¬μŠ€νŠΈ 방식)

감자 πŸ₯” 2021. 7. 23. 18:29
λ°˜μ‘ν˜•

-- λ³Έ ν¬μŠ€νŒ…μ€ 이것이 취업을 μœ„ν•œ μ½”λ”© ν…ŒμŠ€νŠΈλ‹€ with 파이썬 책을 μ°Έκ³ ν•˜μ—¬ μž‘μ„±λ˜μ—ˆμŠ΅λ‹ˆλ‹€.

1. νƒμƒ‰μ΄λž€

  • λ§Žμ€ μ–‘μ˜ 데이터 μ€‘μ—μ„œ μ›ν•˜λŠ” 데이터λ₯Ό μ°ΎλŠ” κ³Όμ •
  • λŒ€ν‘œμ μΈ 탐색 μ•Œκ³ λ¦¬μ¦˜μ€ DFS 와 BFSκ°€ 있음

 

2. κ·Έλž˜ν”„ ν‘œν˜„ 방식

  • κ·Έλž˜ν”„μ˜ ꡬ성 : λ…Έλ“œ(정점), κ°„μ„ (Edge)

  • κ·Έλž˜ν”„λ₯Ό μ½”λ“œλ‘œ ν‘œν˜„ν•˜λŠ” 방법은 2가지가 μžˆλ‹€

 

2.1 인접행렬 ν‘œν˜„ 방식

  • 2차원 λ°°μ—΄λ‘œ κ·Έλž˜ν”„μ˜ 연결관계λ₯Ό ν‘œν˜„ν•˜λŠ” 방식이닀.
  • μ•„λž˜ κ·Έλž˜ν”„λ₯Ό ν‘œλ‘œ ν‘œν˜„ν•˜λ©΄ 였λ₯Έμͺ½μ˜ ν‘œμ²˜λŸΌ ν‘œν˜„μ΄ 될 것이닀.

  • 이 κ·Έλž˜ν”„λ₯Ό 2차원 리슀트둜 κ΅¬μ„±ν•˜κ²Œ 되면 μ•„λž˜μ™€ κ°™λ‹€
INF = 999999  #λ¬΄ν•œλŒ€μ˜ λΉ„μš© μ„ μ–Έ

#2차원 배열을 ν™œμš©ν•˜μ—¬ κ·Έλž˜ν”„λ₯Ό ν‘œν˜„
graph = [
    [0, 7, 5],
    [7, 0 INF],
    [5, INF, 0]
    ]
   
print(graph)
## 결괏값 ---> [[0, 7, 5] , [7, 0, 999999], [5, 999999, 0]]

 

2.2 μΈμ ‘λ¦¬μŠ€νŠΈ 방식

  • 리슀트둜 κ·Έλž˜ν”„μ˜ μ—°κ²° 관계λ₯Ό ν‘œν˜„ν•˜λŠ” 방식

  • ν•΄λ‹Ή κ·Έλž˜ν”„λ₯Ό 인접 리슀트둜 ν‘œν˜„ν•˜κΈ° μœ„ν•œ κ°œλ…μ€ μ•„λž˜μ™€ κ°™λ‹€.

  • 이것을 ν”„λ‘œκ·Έλž˜λ° μ½”λ“œλ‘œ ν‘œν˜„ν•˜λ©΄ μ•„λž˜μ™€ κ°™λ‹€.
#row κ°€ 3개인 2차원 리슀트둜 μ—°κ²° λ¦¬μŠ€νŠΈκ°€ ν‘œν˜„λœλ‹€. (row수 = node 수)
graph = [[] for _ in range(3)]

#λ…Έλ“œκ°€ 0인 μ—°κ²° λ…Έλ“œ 정보 (λ…Έλ“œ, 거리)둜 ν‘œν˜„
graph[0].append((1,7))
grpah[0].append((2,5))
#λ…Έλ“œ 1
graph[1].append((0, 7))
#λ…Έλ“œ 2
graph[2].append((0,5))


print(graph)
## κ²°κ³Ό ---> [[(1,7), (2,5)], [(0,7)], [(0,5)]]

 

2.3 인접행렬과 μΈμ ‘λ¦¬μŠ€νŠΈμ˜ 차이

  • λ©”λͺ¨λ¦¬ μΈ‘λ©΄
    • 인접행렬 : λͺ¨λ“  관계λ₯Ό μ €μž₯ν•˜λ―€λ‘œ λ…Έλ“œ κ°œμˆ˜κ°€ λ§Žμ„γ…‡ 수둝 λ©”λͺ¨λ¦¬κ°€ λΆˆν•„μš”ν•˜κ²Œ 낭비됨
    • μΈμ ‘λ¦¬μŠ€νŠΈ : μ—°κ²°λœ μ •λ³΄λ§Œμ„ μ €μž₯ν•˜κΈ° λ•Œλ¬Έμ— λ©”λͺ¨λ¦¬λ₯Ό 효율적으둜 μ‚¬μš©ν•  수 있음.
  • 속도 μΈ‘λ©΄ 
    • 인접행렬 : λͺ¨λ“  관계λ₯Ό μ €μž₯ν•˜λ―€λ‘œ 두 λ…Έλ“œκ°€ μ—°κ²°λ˜μ–΄ μžˆλŠ”μ§€μ— λŒ€ν•œ 정보λ₯Ό μ–»λŠ” 속도가 λΉ λ₯΄λ‹€
    • μΈμ ‘λ¦¬μŠ€νŠΈ : μ—°κ²°λœ μ •λ³΄λ§Œμ„ μ €μž₯ν•˜κΈ° λ•Œλ¬Έμ— 두 λ…Έλ“œκ°€ μ—°κ²°λ˜μ–΄ μžˆλŠ”μ§€μ— λŒ€ν•œ 정보λ₯Ό μ–»λŠ” 속도가 λŠλ¦¬λ‹€. μ—°κ²°λœ 데이터λ₯Ό ν•˜λ‚˜ν•˜λ‚˜ λ‹€ 확인해 보아야 ν•œλ‹€.
λ°˜μ‘ν˜•