BFS 1
[μ•Œκ³ λ¦¬μ¦˜] BFS(Breadth First Search)

BFSλž€? - 큐λ₯Ό 톡해 κ΅¬ν˜„μ΄ κ°€λŠ₯ν•˜λ‹€. - λ…Έλ“œλ₯Ό λ°©λ¬Έν•˜λ©΄μ„œ μΈμ ‘ν•œ λ…Έλ“œ 쀑 λ°©λ¬Έν•˜μ§€ μ•Šμ•˜λ˜ λ…Έλ“œμ˜ μ •λ³΄λ§Œ 큐에 λ„£κ³ , 큐어 λ“€μ–΄μžˆλ˜ λ…Έλ“œλΆ€ν„° λ°©λ¬Έν•œλ‹€. - νŒŒμ΄μ¬μ—μ„œ 큐λ₯Ό κ΅¬ν˜„ν•  λ•Œ, listλ₯Ό μ‚¬μš©ν•˜λŠ” κ²½μš°κ°€ λŒ€λΆ€λΆ„μΈλ°. list.pop(0)은 μ‹œκ°„λ³΅μž‘λ„κ°€ O(N)이기 λ•Œλ¬Έμ— μ΄λ ‡κ²Œ κ΅¬ν˜„ν•  경우 μ‹œκ°„μ μœΌλ‘œ λΉ„νš¨μœ¨μ μ΄λ‹€. λ”°λΌμ„œ collections 라이브러리의 dequeλ₯Ό μ‚¬μš©ν•˜λ©΄ μ‹œκ°„μ„ μ ˆμ•½ν•  수 μžˆλ‹€. - λ˜ν•œ μΈμ ‘ν•œ λ…Έλ“œ 쀑 λ°©λ¬Έν•˜μ§€ μ•Šμ•˜λ˜ λ…Έλ“œλ₯Ό 큐에 넣을 λ•ŒλŠ” set 데이터 νƒ€μž…μ„ μ΄μš©ν•˜λ©΄ μ‰½κ²Œ κ΅¬ν˜„ν•  수 μžˆλ‹€. 타이틀 μž…λ ₯λΆ€λΆ„2 BFS κ΅¬ν˜„ - λ™μž‘ κ³Όμ • 1) root λ…Έλ“œλΆ€ν„° μ‹œμž‘ν•˜κΈ° μœ„ν•΄ deque에 rootλ₯Ό λ„£λŠ”λ‹€. 2) 큐가 빌 λ–„κΉŒμ§€ loopλ₯Ό λŒλ¦°λ‹€. 3) 큐의 λ§¨μ•ž λ…Έλ“œλ₯Ό..
ΰ­¨β”ˆβ”ˆβ”ˆ Studyβ”ˆβ”ˆβ”ˆΰ­§/β†˜ Algorithm 2021.05.12
1
더보기

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”