CodeGym/ํ–‰๋™/Python SELF KO/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (BFS)

๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (BFS)

์‚ฌ์šฉ ๊ฐ€๋Šฅ

8.1 BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ž‘๋™ ์›๋ฆฌ

๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ (Breadth-First Search, BFS)๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์ˆœํšŒํ•˜๊ฑฐ๋‚˜ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์‹œ์ž‘ ์ •์ ์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ํ˜„์žฌ ๋ ˆ๋ฒจ์— ์žˆ๋Š” ๋ชจ๋“  ์ธ์ ‘ ์ •์ ์„ ํƒ์ƒ‰ํ•œ ํ›„ ๋‹ค์Œ ๋ ˆ๋ฒจ์˜ ์ •์ ์œผ๋กœ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹จ๊ณ„:

  1. ์„ ํƒ๋œ ์‹œ์ž‘ ์ •์ ์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ํ์— ๋„ฃ์Šต๋‹ˆ๋‹ค.
  2. ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋‹ค์Œ์„ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค:
    • ํ์˜ ๋งจ ์•ž์—์„œ ์ •์ ์„ ๊บผ๋‚ด์–ด ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ํ‘œ์‹œํ•ฉ๋‹ˆ๋‹ค.
    • ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ ์ •์ ์„ ๋ชจ๋‘ ํ์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
  3. ์‹œ์ž‘ ์ •์ ์—์„œ ๋„๋‹ฌ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์ •์ ์„ ๋ฐฉ๋ฌธํ•  ๋•Œ๊นŒ์ง€ 2๋‹จ๊ณ„๋ฅผ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค.

์‹œ๊ฐํ™”:

์‹œ๊ฐ„ ๋ณต์žก๋„:

O(V + E) ์—ฌ๊ธฐ์„œ V๋Š” ์ •์ ์˜ ์ˆ˜, E๋Š” ๊ฐ„์„ ์˜ ์ˆ˜์ž…๋‹ˆ๋‹ค.

๊ทธ๋ž˜ํ”„์˜ ๋ชจ๋“  ๋…ธ๋“œ์™€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ์”ฉ ๋ฐฉ๋ฌธ๋ฉ๋‹ˆ๋‹ค.

๊ณต๊ฐ„ ๋ณต์žก๋„:

O(V), ํ์— ์ •์ ์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉ๋˜๋ฉฐ, ์ƒํƒœ(๋ฐฉ๋ฌธํ•œ ์ •์ )๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฐ์—ด๋„ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

8.2 ํ๋ฅผ ํ™œ์šฉํ•œ BFS ๊ตฌํ˜„

๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์€ ํ์™€ ๊ฐ™์€ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ํšจ๊ณผ์ ์œผ๋กœ ๊ตฌํ˜„๋ฉ๋‹ˆ๋‹ค.

ํ๋ฅผ ์‚ฌ์šฉํ•œ BFS ๊ตฌํ˜„:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # ๋…ธ๋“œ ์ฒ˜๋ฆฌ

            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# ์‚ฌ์šฉ ์˜ˆ์‹œ:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 ์–‘๋ฐฉํ–ฅ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰

BFS๋Š” ์ข…์ข… ๊ฒŒ์ž„์—์„œ ๋‘ ์ง€์  ๊ฐ„์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์„ ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋Š” ๋‘ ์ •์  ์‚ฌ์ด์˜ ๊ทธ๋ž˜ํ”„ ๊ฒฝ๋กœ ํƒ์ƒ‰ ๋ฌธ์ œ๋กœ ์‰ฝ๊ฒŒ ๋ณ€ํ™˜๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„์˜ ๊ฐ„์„ ์€ ์ง€๋„์—์„œ์˜ ๋ชจ๋“  ํ†ต๊ณผ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ์ž…๋‹ˆ๋‹ค.

ํ•˜์ง€๋งŒ ๋” ๋น ๋ฅด๊ฒŒ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ๋‘ ๋์—์„œ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด ์–‘๋ฐฉํ–ฅ BFS๊ฐ€ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

์ž‘๋™ ์›๋ฆฌ

์–‘๋ฐฉํ–ฅ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ (Bidirectional BFS)์€ BFS๋ฅผ ์ตœ์ ํ™”ํ•œ ๋ฒ„์ „์œผ๋กœ, ์‹œ์ž‘ ์ •์ ๊ณผ ๋ชฉํ‘œ ์ •์ ์—์„œ ๊ฐ๊ฐ ๋‘ ๊ฐœ์˜ ๋ณ‘๋ ฌ ๊ทธ๋ž˜ํ”„ ์ˆœํšŒ๋ฅผ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ๋‘ ์ˆœํšŒ๊ฐ€ ๊ต์ฐจ๋  ๋•Œ๊นŒ์ง€ ์ง„ํ–‰๋˜๋ฉฐ, ์ด๋Š” ์ „ํ†ต์ ์ธ BFS์— ๋น„ํ•ด ํ›จ์”ฌ ์ ์€ ์ •์ ๊ณผ ๊ฐ„์„ ์„ ๊ฒ€์‚ฌํ•˜๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹จ๊ณ„:

  • ์‹œ์ž‘ ์ •์ ์—์„œ์˜ ์ˆœํšŒ๋ฅผ ์œ„ํ•œ ํ์™€ ๋ชฉํ‘œ ์ •์ ์—์„œ์˜ ํ ๋‘ ๊ฐœ๋ฅผ ์ดˆ๊ธฐํ™”ํ•ฉ๋‹ˆ๋‹ค.
  • ๋‘ ๋ฐฉํ–ฅ์—์„œ์˜ ๋ฐฉ๋ฌธํ•œ ์ •์ ์„ ์ถ”์ ํ•˜๊ธฐ ์œ„ํ•ด ๋‘ ๊ฐœ์˜ ๋ฐฉ๋ฌธ ์ •์  ์ง‘ํ•ฉ์„ ์ดˆ๊ธฐํ™”ํ•ฉ๋‹ˆ๋‹ค.
  • ๋‘ ํ๋กœ๋ถ€ํ„ฐ ๋ฒˆ๊ฐˆ์•„ ๊ฐ€๋ฉฐ ๊ทธ๋ž˜ํ”„๋ฅผ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฐ ๋‹จ๊ณ„์—์„œ ๋ฐฉ๋ฌธํ•œ ์ •์  ์ง‘ํ•ฉ์ด ๊ต์ฐจํ•˜๋Š”์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ๊ต์ฐจ๊ฐ€ ๋ฐœ๊ฒฌ๋˜๋ฉด ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.
  • ๊ต์ฐจ ๋…ธ๋“œ๊ฐ€ ๋ฐœ๊ฒฌ๋˜๊ฑฐ๋‚˜ ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๊ณผ์ •์„ ๊ณ„์†ํ•ฉ๋‹ˆ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

์ตœ์ƒ์˜ ๊ฒฝ์šฐ: O(2 * (V + E)) = O(V + E), ์—ฌ๊ธฐ์„œ V๋Š” ์ •์ ์˜ ์ˆ˜, E๋Š” ๊ฐ„์„ ์˜ ์ˆ˜์ž…๋‹ˆ๋‹ค.

์–‘๋ฐฉํ–ฅ BFS๋Š” ํฐ ๊ทธ๋ž˜ํ”„์—์„œ ๋‹จ๋ฐฉํ–ฅ BFS๋ณด๋‹ค ์ผ๋ฐ˜์ ์œผ๋กœ ๋” ์ ์€ ์ •์ ์„ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.

๊ณต๊ฐ„ ๋ณต์žก๋„:

O(V) ๋‘ ํ์™€ ๋‘ ๊ฐœ์˜ ๋ฐฉ๋ฌธ ์ •์  ์ง‘ํ•ฉ์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

์–‘๋ฐฉํ–ฅ BFS์˜ ์˜ˆ์ œ ๊ตฌํ˜„

์˜ˆ์‹œ๋Š” ๋งค์šฐ ๊ธธ๊ธฐ ๋•Œ๋ฌธ์— ๋‹จ๋ฐฉํ–ฅ ํƒ์ƒ‰๋ณด๋‹ค ์„ธ ๋ฐฐ ์ •๋„ ๊ธธ์–ด์„œ ์—ฌ๊ธฐ์„œ๋Š” ์ƒ๋žตํ•ฉ๋‹ˆ๋‹ค. ๋‚˜์ค‘์— ํ•„์š”ํ•  ๋•Œ๋Š” ์Šค์Šค๋กœ ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ์„ ๊ฒ๋‹ˆ๋‹ค.

8.4 BFS๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ ์˜ˆ์‹œ

BFS๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์ „ํ˜•์ ์ธ ๋ฌธ์ œ ์˜ˆ์‹œ:

1. ๋ฌดํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ์ตœ๋‹จ ๊ฒฝ๋กœ ์ฐพ๊ธฐ:

BFS๋Š” ์‹œ์ž‘ ์ •์ ์—์„œ ๋ชฉํ‘œ ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ(์ตœ์†Œ ๊ฐ„์„  ์ˆ˜)๋ฅผ ์ฐพ๋Š” ๋ฐ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

์ ์šฉ ๋ถ„์•ผ:

  • ๋„ค๋น„๊ฒŒ์ด์…˜ ์‹œ์Šคํ…œ์—์„œ ์ง€์  ๊ฐ„ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด.
  • ๋„คํŠธ์›Œํฌ ๋ถ„์„์—์„œ ๋ฐ์ดํ„ฐ ์ „์†ก์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด.

2. ๊ทธ๋ž˜ํ”„ ์—ฐ๊ฒฐ์„ฑ ๊ฒ€์‚ฌ:

๊ทธ๋ž˜ํ”„๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š”์ง€, ์ฆ‰ ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ํ™•์ธ.

์ ์šฉ ๋ถ„์•ผ:

  • ๋„คํŠธ์›Œํฌ ๋ถ„์„์—์„œ ๋„คํŠธ์›Œํฌ์˜ ์—ฐ๊ฒฐ์„ฑ์„ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด.
  • ์†Œ์…œ ๋„คํŠธ์›Œํฌ ๋ถ„์„์—์„œ ์‚ฌ์šฉ์ž ๊ทธ๋ฃน์˜ ์—ฐ๊ฒฐ์„ฑ์„ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด.

3. ๋ฏธ๋กœ ์ƒ์„ฑ:

BFS๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ฃผ์–ด์ง„ ์†์„ฑ์„ ๊ฐ€์ง„ ๋žœ๋ค ๋ฏธ๋กœ ์ƒ์„ฑ.

์ ์šฉ ๋ถ„์•ผ:

  • ๊ฒŒ์ž„ ์• ํ”Œ๋ฆฌ์ผ€์ด์…˜์—์„œ ๋ฏธ๋กœ๋ฅผ ์ƒ์„ฑํ•˜๊ธฐ ์œ„ํ•ด.
  • ๋กœ๋ด‡ ๊ณตํ•™์—์„œ ๋‚ด๋น„๊ฒŒ์ด์…˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ…Œ์ŠคํŠธ๋ฅผ ์œ„ํ•ด.

4. ํŠธ๋ฆฌ์—์„œ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰:

BFS๋Š” ํŠธ๋ฆฌ๋ฅผ ์ˆœํšŒํ•˜์—ฌ ํŠธ๋ฆฌ์˜ ๊ฐ ๋ ˆ๋ฒจ์—์„œ ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค (์˜ˆ: ๊ฐ ๋ ˆ๋ฒจ์˜ ๋ชจ๋“  ๋…ธ๋“œ ์ถœ๋ ฅ).

์ ์šฉ ๋ถ„์•ผ:

  • ๋ฐ์ดํ„ฐ ์‹œ๊ฐํ™” ๋ฌธ์ œ์—์„œ ๋ ˆ๋ฒจ๋ณ„๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ํ‘œ์‹œํ•ด์•ผ ํ•  ๋•Œ.
  • ๊ณ„ํš ๋ฌธ์ œ์—์„œ ๊ณ„์ธต ๊ตฌ์กฐ์˜ ๊ฐ ๋ ˆ๋ฒจ์—์„œ ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•  ๋•Œ.

5. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ๊ฒ€์‚ฌ:

๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€, ์ฆ‰ ๋‘ ๊ฐœ์˜ ์ง‘ํ•ฉ์œผ๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๊ณ , ๊ฐ„์„ ์ด ์„œ๋กœ ๋‹ค๋ฅธ ์ง‘ํ•ฉ์˜ ์ •์  ์‚ฌ์ด์—๋งŒ ์กด์žฌํ•˜๋Š”์ง€๋ฅผ ํ™•์ธ.

์ ์šฉ ๋ถ„์•ผ:

  • ๊ทธ๋ž˜ํ”„ ์ด๋ก ์—์„œ ๊ทธ๋ž˜ํ”„์˜ ์ด๋ถ„์„ฑ์„ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด.
  • ๊ทธ๋ž˜ํ”„ ์ปฌ๋Ÿฌ๋ง ๋ฌธ์ œ์—์„œ ๊ทธ๋ž˜ํ”„๋ฅผ ๋‘ ๊ฐ€์ง€ ์ƒ‰์œผ๋กœ ์น ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด.
2
๊ณผ์ œ
Python SELF KO,  ๋ ˆ๋ฒจ 56๋ ˆ์Šจ 2
์ž ๊ธˆ
์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„: BFS ๋ฒ„์ „
์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„: BFS ๋ฒ„์ „
2
๊ณผ์ œ
Python SELF KO,  ๋ ˆ๋ฒจ 56๋ ˆ์Šจ 2
์ž ๊ธˆ
์ตœ๋‹จ ๊ฒฝ๋กœ: BFS ๋ฒ„์ „
์ตœ๋‹จ ๊ฒฝ๋กœ: BFS ๋ฒ„์ „
์ฝ”๋ฉ˜ํŠธ
  • ์ธ๊ธฐ
  • ์‹ ๊ทœ
  • ์ด์ „
์ฝ”๋ฉ˜ํŠธ๋ฅผ ๋‚จ๊ธฐ๋ ค๋ฉด ๋กœ๊ทธ์ธ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค
์ด ํŽ˜์ด์ง€์—๋Š” ์•„์ง ์ฝ”๋ฉ˜ํŠธ๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค