코딩테스트 준비/알고리즘

BFS - 백준 1260 파이썬

갑자기 내리는 비 2021. 5. 20. 17:36

BFS란 Breadth-First Search의 약자로, 너비 우선 탐색이라고 합니다.

 

단어에서 볼 수 있듯 BFS는 DFS( 깊이 우선 탐색 )처럼 깊게 가는것이 아닌, 주변의 노드만 확인하는 방식으로 구현됩니다.

 

아래의 이미지로 설명하겠습니다.

 

동작 방식 

1. 큐에 저장된 첫번째 노드를 저장합니다.

2. 현재 노드에 방문했다는 표시를 합니다.

3. 큐에 저장된 첫번째 노드를 추출해 인접했지만 방문한 적 없는 노드를 찾습니다.

4. 찾은 노드를 큐(Queue)에 저장합니다.( Queue에대한 설명은 이전글에 정리하였습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.

큐에 저장된 노드가 없을때까지 3~5과정을 반복합니다.

 

 

하나씩 순서대로 진행시켜보겠습니다.

1. 시작노드(1)를 큐에 저장하고 출력합니다.

2. 시작노드(1)를 방문했다고 표시합니다.(visit[1]=False , 리스트를 모두 True로 초기화한 상태입니다.)

3. 큐에 저장된 첫번째 노드(1)를 추출해 인접했지만 방문한 적 없는 노드를(2,3,4) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 2, 3, 4가 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4)

 

3. 큐에 저장된 첫번째 노드(2)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를(5,6) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 3, 4, 5, 6이 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4, 5, 6 )

 

3. 큐에 저장된 첫번째 노드(3)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를(7) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 4, 5, 6, 7이 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4, 5, 6, 7 )

 

3. 큐에 저장된 첫번째 노드(4)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를(8) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 5, 6, 7, 8이 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4, 5, 6, 7, 8 )

 

3. 큐에 저장된 첫번째 노드(5)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를(9) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 6, 7, 8, 9가 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4, 5, 6, 7, 8, 9 )

 

3. 큐에 저장된 첫번째 노드(6)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를 찾습니다.

연결된 노드가 없으므로 패스합니다.( 현재 큐에는 7, 8, 9가 있습니다. )

 

3. 큐에 저장된 첫번째 노드(7)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를(10, 11) 찾습니다.

4. 찾은 노드를 큐에 저장합니다. ( 현재 큐에는 8, 9, 10, 11이 있습니다. )

5. 해당 노드에 방문했다는 표시를 남깁니다.( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 )

 

3. 큐에 저장된 첫번째 노드(8)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를 찾습니다.

연결된 노드가 없으므로 패스합니다.( 현재 큐에는 9, 10, 11이 있습니다. )

 

3. 큐에 저장된 첫번째 노드(9)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를 찾습니다.

연결된 노드가 없으므로 패스합니다.( 현재 큐에는 10, 11이 있습니다. )

 

3. 큐에 저장된 첫번째 노드(10)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를 찾습니다.

연결된 노드가 없으므로 패스합니다.( 현재 큐에는 11이 있습니다. )

 

3. 큐에 저장된 첫번째 노드(11)를 추출해 출력하고, 인접했지만 방문한 적 없는 노드를 찾습니다.

연결된 노드가 없으므로 패스합니다.( 현재 큐에는 아무것도 없습니다. )

 

큐에 더이상 데이터가 없으므로 종료합니다.

 

입력 :

4 5 1

1 2

1 3

1 4

2 4

3 4

//  4 5 1은 순서대로 노드의 수, 간선의 수, 시작하는 노드의 번호입니다.

// 밑의 숫자들은 어떤 노드가 연결되었는지 입력하는 것입니다.

// ex) 1 2   ==  1과 2노드가 연결되어있다는 것입니다.

 

전의 DFS에서 한 것처럼 NxN행렬로 만들어 문제를 풀었습니다.

from collections import deque
from sys import stdin

def bfs(node_num):
    # 큐에 첫번째 노드를 저장합니다.
    queue.append(node_num)
    # 방문했다는 표시를 합니다.
    visit[node_num] = False
    
    # 큐에 저장된 데이터가 없을때까지 수행합니다.
    while(queue):
        # 큐의 첫번째 노드를 추출합니다.
        node_num = queue.popleft()
        # 출력합니다.
        print(node_num, end=' ')
        
        # 연결된 노드가 있는지 전체 노드를 확인합니다.
        for i in range(1, node + 1):
            # 방문하지 않았는데 연결되어있다면
            if visit[i] == True and s[node_num][i] == True:
                # 큐에 저장한 후 방문표시를 합니다.
                queue.append(i)
                visit[i] = False

queue = deque()
node, edge, start = map(int, stdin.readline().split())

# True False로 NxN행렬을 만듭니다.
s = [[False] * (node + 1) for i in range(node + 1)]
visit = [True for i in range(node + 1)]

# 입력받은 좌표들만 연결되어있다고 표시를 해줍니다.
for i in range(edge):
    x, y = map(int, stdin.readline().split())
    s[x][y] = True
    s[y][x] = True

bfs(start)