Baekjoon 11724 | 연결요소의 개수 (Python)

📌문제

SILVER2 / 그래프 / 그래프 탐색 / BFS / DFS

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

📌문제 분석 및 설계

dfs를 몰라서 개념공부할겸 정한 문제이다.

bfs도 적용가능해서 두 버전으로 코드를 돌려봤다.

 

아래 코드에 있는 DFS와 BFS가 딱 해당 알고리즘의 코드이니, 모르시는 분들은 우선 냅다 외워둬도 괜찮을 것 같다.

 

중요했던건 sys.setrecursionlimit(10**6)  해당 코드를 안넣으면 백준에서 계속 런타임에러가 났다.. 

기억하기 ..

📌소스 코드

 

DFS버전

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited=[0]*(N+1)
def dfs(start):
    visited[start]=1
    for new in graph[start]:
        if not visited[new]:
            dfs(new)

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

 

BFS버전

import sys
from collections import deque

input=sys.stdin.readline
N,M=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited=[0]*(N+1)
def bfs(start):
    q=deque([start])
    visited[start]=1
    while q:
        node=q.popleft()
        for new in graph[node]:
            if not visited[new]:
                q.append(new)
                visited[new]=1

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