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

📌문제 유형

그래프이론, 그래프탐색, DFS, BFS (실버2)

 

📌문제

11724번: 연결 요소의 개수

 

📌나의 문제풀이

- 시간초과

n,m = map(int,input().split())

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

parent = [i for i in range(n+1)]
link = []
for _ in range(m):
    u,v = map(int,input().split())
    link.append((u,v))
    union_parent(parent, u, v)

for j in range(m):
    union_parent(parent, link[j][0], link[j][1])

print(len(set(parent[1:])))

- 전형적인 DFS 문제로 해결

• graph에 양방향 값 넣기
• 이미 방문했다면, return / 이외는 DFS 탐색
• DFS 끝난 탐색은 하나의 graph완성이므로 ans 더하기

n,m = map(int,input().split())

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

ans = 0
def dfs(a,visited):
    if visited[a] == True:
        return
    
    visited[a] = True
    
    for num in graph[a]:
        if not visited[num]:
            dfs(num,visited)
        else:
            continue


for j in range(1,n+1):
    if visited[j] == True:
        continue
    else:
        dfs(j,visited)
        ans += 1
print(ans)

 

📌 다른사람의 문제풀이

- 아무것도 연결되지 않은 단독 노드도 처리

백준 11724번 파이썬 문제풀이(큐와 그래프 - 연결 요소의 개수) - DFS, BFS

import sys

sys.setrecursionlimit(5000)
input = sys.stdin.readline


# dfs로 그래프를 탐색한다.
def dfs(start, depth):

    #해당 노드 방문체크 한다.
    visited[start] = True

    # 해당 시작점을 기준으로 계속해서 dfs로 그래프를탐색한다.
    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)


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

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

# 방문처리
visited = [False] * (1 + N)
count = 0  # 컴포넌트 그래프 개수 저장

# 1~N번 노드를 각각돌면서
for i in range(1, N + 1):
    if not visited[i]:  # 만약 i번째 노드를 방문하지 않았다면
        if not graph[i]:  # 만약 해당 정점이 연결된 그래프가 없다면
            count += 1  # 개수를 + 1
            visited[i] = True  # 방문 처리
        else:  # 연결된 그래프가 있다면
            dfs(i, 0)  # dfs탐색을 돈다.
            count += 1  # 개수를 +1

print(count)

 

📌 리뷰

- 같은 코드로 Python3를 돌렸을 때, recursion error 발생했는데 PyPy3에서는 정답

•  " python 재귀 허용치 늘리기 위해 sys.setrecursionlimit(10000) 작성"

연결 요소의 개수-백준 11724번(python)