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

💡문제 분석 요약

• 입력 한 값을 그래프로 만들었을 때, 만들어지는 그래프의 수를 출력

💡알고리즘 설계

• DFS 함수와 BFS 함수를 작성
• visited => 7 까지 하는 이유 : 노드에 0이 없기 때문
• 1~7까지 방문하지 않은 노드는 방문시작하도록 dfs/bfs시작
• dfs/bfs가 끝나면 count ++

💡변경한 코드

[DFS]
import sys
input = sys.stdin.readline

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

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        count += 1 # dfs 한 번 끝날 때마다 count+1

print(count)



[BFS]
from collections import deque

# bfs 함수
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        bfs(graph, i, visited) # bfs 한 번 끝날 때마다 count+1
        count += 1

print(count)

💡시간복잡도

O(N+M)

💡 틀린 이유

for 문을 돌면서 false였던게 true로 변경될 수도 있는데, 무작정 for문에서 false의 값을 체크하여 cnt++ 하려했다.

💡 틀린 부분 수정 or 다른 풀이

다시 풀어야지 ..

💡 느낀점 or 기억할정보

다시 풀어야지 ..