[백준] 11724번 연결 요소의 개수

문제 내용

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

풀이 과정

-유니온 파인드와 그래프탐색(BFS) 이렇게 두가지 방향성을 생각함.

-유니온 파인드 같은 경우는 유니온 과정에서 적절하지 않다고 판단하여 BFS로 진행하기로 했음.

풀이중 문제점

1.deque 사용의 미숙함

 

문제점 해결 과정

1.deque에 대해 학습을 진행한후 풀이 진행.

=> 차후 deque관련 포스트 작성으로 학습 예정

해결 코드

import sys
from collections import deque
 
sys_input=sys.stdin.readline
n,m=map(int,sys_input().rstrip().split())
arr=[[]*(n+1) for _ in range(n+1)]
visited=[False]*(n+1)
 
for _ in range(m): #인접행렬
    a,b=map(int,sys_input().rstrip().split())
    arr[a].append(b)
    arr[b].append(a)
 
ans=0
 
def bfs(x): #BFS
    q=deque()
    q.append(x)
    while len(q)!=0:
        c=q.pop()
        for n in arr[c]:
            if not visited[n]:
                visited[n]=True
                q.append(n)
 
for i in range(1,n+1):
    if not visited[i]:
        ans+=1
        bfs(i)    
 
print(ans)

주요 개념 

• 그래프 탐색: 너비 우선 탐색(Breadth-First Search,BFS)