<2022모각코/TIL> [백준/python] 연결 요소의 개수 (BFS)

백준 11724번을 python으로 풀어보았다.

11724번: 연결 요소의 개수

from collections import deque

node, line_num = tuple(map(int, input().split()))
line = [tuple(map(int, input().split())) for _ in range(line_num)]
line = deque(line)

def bfs(first, line, line_num, check, node):
    que = deque()
    answer = 0
    rst = 0
    que.append(first)

    while 1
        x, y = que.popleft()
        for i in range(line_num - 1):
            if check[i] and (x in line[i]) or (y in line[i]):
                que.append(line[i])
                check[i] = False
                if rst == 1:
                    answer += 1
                    rst = 0
        if len(que) == 0:
            for i in range(line_num - 1):
                if check[i] == True:
                    que.append(line[i])
                    check[i] = False
                    rst = 1
                    break
        if True not in check:
            break
        print(que, check, answer, rst)    
    if rst == 0:
        answer += 1
    return answer

first = line.popleft()
print(bfs(first, line, line_num, [True for _ in range(line_num - 1)], node))

2시간동안 풀어보았었으나 시간 초과가 났다. 그래도 알고리즘을 설명해 보자면 bfs로 풀고 있었으며, 처음 간선을 bfs에 넣은 후, 방향이 없는 그래프임으로 만약 원소중 하나가 있다면 큐에 넣고, 빼는 것을 반복하였으나... 왜인지 모르게 계속 무한 루프가 난다. 향후 개선이 필요하다.

 

from collections import deque
 
def bfs():
    queue = deque([start])
    b_check = [False for _ in range(n + 1)]
    b_check[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in edge[v]:
            if not b_check[i]:
                b_check[i] = True
                queue.append(i)

파이썬에서는 이렇게 bfs를 구현할 수 있으며, 이것이 그나마 시간 복잡도가 가장 나은 방법인 것 같다.