완전탐색★BFS★전력망 둘로 나누★[프로그래머스]

전력망 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

==> BFS 로 풀어야 한다!!

EX)

    A
   / \
  B   C
 / \      \
D   E   F

 

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

 

from collections import deque

def bfs(graph, start):
    visited = []  # 방문한 노드를 저장할 리스트
    queue = deque([start])  # 탐색할 노드를 저장하는 큐

    while queue:
        node = queue.popleft()  # 큐의 맨 앞에서 노드를 꺼냄
        if node not in visited:
            visited.append(node)  # 방문 처리
            neighbors = graph[node]  # 현재 노드의 인접한 노드들
            for neighbor in neighbors:
                queue.append(neighbor)  # 큐에 인접한 노드들 추가

    return visited

start_node = 'A'
result = bfs(graph, start_node)
print("BFS traversal:", result)

bfs(graph , start) 실행 프로세스

 

1. visited = []

2. queue =  deque( ['A'] ) 

 

First)

3. while queue = ['A'] :

 

4. node = queue.popleft() ==> 'A'                                                             

 

5. node = 'A' not in visited :

 

6-1. visited.append(node) ==> visited = ['A']

 

6-2. neighbors = graph['A'] = ['B' , 'C']

 

6-2-1. for neighbor in neighbors: 

 

6-2-2. queue.append( 'B')

 

6-2-2. queue.append('C')

 

Second)

 

3. node = queue.popleft() ==> 'B'

 

4. node = 'B' not in visitied :

 

5-1. visisited.append(node) ==> visited = ['A' ,'B']

 

5-2 . neighbors = graph ['B']  = ['D' , 'E']

 

5-2-1. for neighbor in neighbors:

 

5-2-2 . queue.append('D')

 

5-2-2 . queue.append('E') 

 

==> queue = ['C' , 'D' , 'E'] 

 

 

 

 

 

BFS traversal: ['A', 'B', 'C', 'D', 'E', 'F']