알고리즘/자료구조 05 - BFS

BFS

• 루트 (시작점)에서 방문점까지의 거리를 알 수 있다.
• 루트의 거리는 0이다.

import sys
from collections import deque

sys.stdin = open("input.txt", 'r')

# 1 2 1 3 1 4 1 5 2 6 2 7 5 6 6 7 6 8 
Data = list(map(int, input().split()))
lenData = int(len(Data)/2)
MyMap = [[0] * (lenData+1) for _ in range(lenData+1)]

for i in range(lenData):
    row = Data[i*2]
    col = Data[i*2+1]
    MyMap[row][col] = 1
    MyMap[col][row] = 1

visited = [0] * (lenData+1)
distance = [0] * (lenData+1)
parent = [0] * (lenData+1)
dq = deque([])

for row in range(1, lenData):
    for col in range(1, lenData):
        print(MyMap[row][col], end='')
    print()

# MyMap
# 01111000
# 10000110
# 10000000
# 10000000
# 10000100
# 01001011
# 01000100
# 00000100

def BFS(here):
    dq.append(here)
    visited[here] = True

    while dq:
        here = dq.popleft()
        print(here, end=' ')
        for next in range(1, lenData+1):
            if MyMap[here][next] and not visited[next]:
                visited[next] = True
                distance[next] = distance[here]+1
                parent[next] = here
                dq.append(next)
BFS(1)
# 1 2 3 4 5 6 7 8