[백준] 11724번 연결 요소의 개수 - 파이썬(Python)

문제 (링크)

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

11724번: 연결 요소의 개수

 

나의 풀이

# BFS 이용
from collections import deque

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

for _ in range(M):
	x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def bfs(v):
	q = deque()
    q.append(v)
    
    while q:
    	x = q.popleft()
        if visited[x] == False:
        	visited[x] = True
            for i in graph[x]:
            	q.append(i)

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

print(cnt)

# DFS 이용

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

for _ in range(M):
	x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def dfs(v):
	visited[v] = True
    for i in graph[v]:
    	if visited[i] == False:
        	dfs(i)

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

print(cnt)

코드 설명 및 풀이법

BFS와 DFS 모두를 사용하여 풀 수 있는 문제이다.

 

왜 그런지 모르겠는데 백준에서 언어를 파이썬으로 선택하고 두 코드를 돌리면 모두 시간초과가 뜨고, PyPy3로 선택하고 돌리면 통과가 된다.

 

몇 가지 다른 문제들에도 비슷한 경우가 있는데 이유를 모르겠다.