𝙂𝙧𝙖π™₯𝙝

uuuouuoΒ·2022λ…„ 7μ›” 22일
κ·Έλž˜ν”„μΈμ ‘λ¦¬μŠ€νŠΈμΈμ ‘ν–‰λ ¬
0
post-thumbnail

πŸ“– κ·Έλž˜ν”„

  • μ•„μ΄ν…œλ“€κ³Ό 이듀 μ‚¬μ΄μ˜ μ—°κ²° 관계 ν‘œν˜„
  • κ·Έλž˜ν”„λŠ” 정점(Vertex)λ“€μ˜ 집합과 이듀을 μ—°κ²°ν•˜λŠ” κ°„μ„ (Ebge)λ“€μ˜ μ§‘ν•©μœΌλ‘œ κ΅¬μ„±λœ 자료 ꡬ쑰
    • V: μ •μ μ˜ 개수, E: κ·Έλž˜ν”„μ— ν¬ν•¨λœ κ°„μ„ μ˜ 개수
    • V개의 정점을 가진 κ·Έλž˜ν”„λŠ” μ΅œλŒ€ V * (V-1) / 2
    • ex) 5개의 정점이 μžˆλŠ” κ·Έλž˜ν”„μΌ λ•Œ μ΅œλŒ€ κ°„μ„  μˆ˜λŠ” 10(5 * 4 / 2)개
  • μ„ ν˜• μžλ£Œκ΅¬μ‘°λ‚˜ 트리 자료ꡬ쑰둜 ν‘œν˜„ν•˜κΈ° μ–΄λ €μš΄ N:N 관계 ν‘œν˜„ κ°€λŠ₯

    μ°Έκ³  ) 자료ꡬ쑰 λΆ„λ₯˜

πŸ’¬ κ·Έλž˜ν”„ μœ ν˜•

β—Ύ 무ν–₯ κ·Έλž˜ν”„

  • λ°©ν–₯μ„± μ—†λŠ” κ·Έλž˜ν”„

β—Ύ 유ν–₯ κ·Έλž˜ν”„

  • λ°©ν–₯μ„± μžˆλŠ” κ·Έλž˜ν”„

β—Ύ κ°€μ€‘μΉ˜ κ·Έλž˜ν”„

  • 간선에 숫자, 이동할 λ•Œ ν•„μš”ν•œ λΉ„μš© ν‘œμ‹œν•œ κ·Έλž˜ν”„

β—Ύ 사이클 μ—†λŠ” λ°©ν–₯ κ·Έλž˜ν”„

  • 경둜λ₯Ό ν‘œμ‹œν–ˆμ„ λ•Œ λŒμ•„μ˜€λŠ” κ²½λ‘œκ°€ μ—†λŠ” κ·Έλž˜ν”„

β—Ύ 사이클 μ—†λŠ” 무ν–₯ κ·Έλž˜ν”„

  • 트리 ν˜•νƒœμ˜ κ·Έλž˜ν”„

β—Ύ μ™„μ „ κ·Έλž˜ν”„

  • 정점듀에 λŒ€ν•΄ κ°€λŠ₯ν•œ λͺ¨λ“  간선듀을 가진 κ·Έλž˜ν”„

β—Ύ λΆ€λΆ„ κ·Έλž˜ν”„

  • μ›λž˜ κ·Έλž˜ν”„μ—μ„œ μΌλΆ€μ˜ μ •μ μ΄λ‚˜ 간선을 μ œμ™Έν•œ κ·Έλž˜ν”„

πŸ’¬ κ·Έλž˜ν”„ κ°œλ… 정리

β—Ύ 인접 정점

  • 인접
    • 두 개의 정점에 간선이 쑴재(μ—°κ²°)ν•˜λ©΄ μ„œλ‘œ μΈμ ‘ν•œλ‹€κ³  함
    • μ™„μ „ κ·Έλž˜ν”„μ— μ†ν•œ μž„μ˜μ˜ 두 정점듀은 λͺ¨λ‘ 인접해 있음

β—Ύ κ·Έλž˜ν”„ 경둜

  • κ²½λ‘œλž€ 간선듀을 μˆœμ„œλŒ€λ‘œ λ‚˜μ—΄ν•œ 것
    • κ°„μ„ λ“€ : (0, 2), (2, 4), (4, 6)
    • 점점듀 : 0 - 2 - 4 - 6
  • λ‹¨μˆœκ²½λ‘œ : 경둜 쀑 ν•œ 정점을 μ΅œλŒ€ν•œ ν•œλ²ˆλ§Œ μ§€λ‚˜λŠ” 경둜
  • 사이클 : μ‹œμž‘ν•œ μ •μ μ—μ„œ λλ‚˜λŠ” 경둜

πŸ’¬ κ·Έλž˜ν”„ ν‘œν˜„

  • κ°„μ„ μ˜ 정보λ₯Ό μ €μž₯ν•˜λŠ” 방식, λ©”λͺ¨λ¦¬λ‚˜ μ„±λŠ₯을 κ³ λ €ν•΄μ„œ κ²°μ •

μ’…λ₯˜

  • 인접행렬 (Adjacent Matrix) : V x V 크기의 2차원 배열을 μ΄μš©ν•΄μ„œ κ°„μ„  정보 μ €μž₯
  • 인접 리슀트 (Adjacent List) : 각 μ •μ λ§ˆλ‹€ ν•΄λ‹Ή μ •μ μœΌλ‘œ κ°€λŠ” κ°„μ„± 정보 μ €μž₯
  • κ°„μ„ μ˜ λ°°μ—΄ : κ°„μ„ (μ‹œμž‘ 정점, 끝 정점)을 배열에 μ—°μ†μ μœΌλ‘œ μ €μž₯

β—Ύ 인접 ν–‰λ ¬

두 정점을 μ—°κ²°ν•˜λŠ” κ°„μ„ μ˜ 유무λ₯Ό ν–‰λ ¬λ‘œ ν‘œν˜„

  • V x V μ •λ°© ν–‰λ ¬
  • ν–‰ λ²ˆν˜Έμ™€ μ—΄ λ²ˆν˜ΈλŠ” κ·Έλž˜ν”„μ˜ 정점 의미
  • 두 정점이 μΈμ ‘λ˜μžˆμœΌλ©΄ 1, μ•„λ‹ˆλ©΄ 0
  • κ°€μ€‘μΉ˜κ°€ μžˆλ‹€λ©΄ κ°€μ€‘μΉ˜ μž‘μ„±

무ν–₯ κ·Έλž˜ν”„μ˜ 인접 ν–‰λ ¬

  • λŒ€κ°μ„ μ„ κΈ°μ€€μ΄λ‘œ λŒ€μΉ­μ΄ 됨

유ν–₯ κ·Έλž˜ν”„μ˜ 인접 ν–‰λ ¬

  • ν–‰ i의 ν•© = 정점 i의 λ‚˜κ°€λŠ” λ°©ν–₯ 개수
  • μ—΄ i의 ν•© = 정점 i의 λ“€μ–΄μ˜€λŠ” λ°©ν–₯ 개수

β—Ύ 인접 리슀트

  • 각 정점에 λŒ€ν•œ 인접 정점듀을 순차적으둜 ν‘œν˜„
  • ν•˜λ‚˜μ˜ 정점에 λŒ€ν•œ 인접 정점듀을 각각 λ…Έλ“œλ‘œ ν•˜λŠ” μ—°κ²° 리슀트둜 μ €μž₯

무ν–₯ κ·Έλž˜ν”„μ˜ 인접 리슀트

유ν–₯ κ·Έλž˜ν”„μ˜ 인접 리슀트

πŸ’‘ 문제 ν’€ λ•Œ Tip

  • μ–΄λ–€ ν•œ μ •μ μ—μ„œ νŠΉμ • μ •μ μœΌλ‘œ κ°€λŠ” 간선이 μžˆλŠ”μ§€ ν™•μΈν•˜κ³  싢을 경우
  • 인접 행렬은 인덱슀λ₯Ό 톡해 λ°”λ‘œ 확인 κ°€λŠ₯
  • 인접 λ¦¬μŠ€νŠΈλŠ” ν•˜λ‚˜μ”© μˆœνšŒν•΄μ•Ό 함

⭐ input이 적을 λ•ŒλŠ” 인접 ν–‰λ ¬λ‘œ ν‘ΈλŠ” 것이 μ’‹κ³ , input이 λ„ˆλ¬΄ 클 경우 λ©”λͺ¨λ¦¬ 문제둜 인접 리슀트 이용

profile
uuuouuo
이전 포슀트

π™π™šπ™œπ™ͺ𝙑𝙖𝙧 𝙀𝙭π™₯π™§π™šπ™¨π™¨π™žπ™€π™£

λ‹€μŒ 포슀트

π™Œπ™ͺπ™šπ™ͺπ™š

0개의 λŒ“κΈ€