[Python][백준] 11724. 연결 요소의 개수/ 그래프 탐색,DFS,BFS (S2)

링크🔗

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

---

🗒️파이썬 코드 풀이 (DFS)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(graph,i,visited):
    visited[i] = True
    for v in graph[i]:
        if not (visited[v]):
            dfs(graph,v,visited)

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0
for i in range(1, N + 1):
    if not (visited[i]):
        dfs(graph,i,visited)
        count += 1

print(count)

 

1. DFS로 푸는 방법에 대해 먼저 알아보자.

 

2. 그래프 탐색이 나올 때, DFS로 풀든 BFS로 풀든 2가지 리스트를 꼭 기억하자

- visited (노드 방문 체크 리스트)
ex )  [ 0, 1, 0, 0, 0 ]   
->  방문 한 특정 인덱스는 1 로 표현

- graph (연결된 간선 리스트)
ex)  1-2 / 1-3 / 2-1  간선 일 때  [[ ], [2,3], [1], [1] ] 로 표현
앞에 있는 [ ] 는 인덱싱을 편하게 하기위해 일부러 놓음

 

이 두개의 리스트만 준비되면, BFS든 DFS든 다 할 수 있다.

 

3. 1 ~ N 까지 반복문을 돌리면서, 순차적으로 방문하지 않은 인덱스를 dfs의 매개변수 i로 전달한다.

 

4. dfs 함수에서 i는 visited 리스트로 가서 방문 표시를 한다. 

그리고 i에 해당하는 graph 리스트의 값들을 반복문 돌리고, 방문하지 않은 노드를 찾아 dfs 함수를 실행한다.

 

🗒️파이썬 코드 풀이 (BFS)

import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bfs(graph, i, visited):
    visited[i] = True
    q = deque([i])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if not (visited[v]):
                q.append(v)
                visited[v] = True


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0
for i in range(1, N + 1):
    if not (visited[i]):
        bfs(graph, i, visited)
        count += 1

print(count)

 

1. 이번에는  BFS 방식으로 푸는 법에 대해 알아보자.

앞서 했던 DFS와 전반적으로 비슷하고, 함수 구현 부분만 좀 다르다. 

 

2. BFS도 똑같이 1 ~ N 까지의 for 문을 돌려주고, 해당하는 인덱스의 방문을 확인한다. 방문하지 않은 경우, 해당 인덱스를 bfs의 매개변수로 넘겨준다.

 

3. bfs 함수에서 전달 받은 매개변수 i로 방문 처리를 하고, Queue 를 만들어 준다. 

(BFS는 Queue 자료 구조 / DFS는 Stack 자료구조 활용)

 

4. 가장 첫 번째 인덱스가 Queue에들어가고, popleft를 통해 리스트에서 빠져 나와 변수 u에 할당된다. u는 graph 리스트의 인덱스가 되어, 해당 위치의 리스트를 반복문으로 돌려준다. 그러면 v는 각각의 노드값이 될 것이고, 이 노드들의 방문 여부를 확인 후 방문하지 않은 경우 Queue 구조에 넣어준 후 방문 체크를 한다. 

 

ex)  정점 : (1-2)  (2-5) (5-1) (3-4) (4-6) 
graph 리스트 : [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]] 

맨 처음 가장 먼저 반복문을 통해 1이 bfs의 매개변수로  전달된다. 
bfs에서 1은 바로 방문 처리 되고 
 -----  [0 , 1, 0 , 0 , 0, 0, 0] 

q에 넣어진다.   
-----   q = [1]

q가 비워질 때 까지 while 문이 돌아간다.
while 문 내에서는 q의 가장 앞 부분을 popleft로 떼워와 u 에 할당한다
 -----  q  =[ ]  /  u = 1 

graph[1]에는 2, 5 정점 노드가 있고,이 노드들을 q에 append 해주고 반복문 처리한다.
----- q = [2, 5]  / [0 , 1, 1 , 0 , 0, 1, 0] 

다시 맨 처음 while 문으로 돌아와  popleft를 통해 정점 2를 graph 인덱스로 활용하면 된다.
이 과정을 q가 비워질 때 까지 반복한다.

 

📌  문제 코멘트

 

그래프 관련 문제는 많이 풀지 못해서, 왠지 보면 겁부터 난다.

그냥 무조건 방문 체크 리스트, 그래프 간선 리스트 부터 기억하자. 

 

특히 그래프 간선 리스트 같은 경우,

해당 정점은 graph 리스트에 넣지 말고 연결된 정점만 이중 리스트에 넣어주면 된다. 

그리고 방문 체크만 잘 하면 끝이다. 

---

📚문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1