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

백준 11724번 <연결 요소의 개수> 문제 보기

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

11724번: 연결 요소의 개수

 

 

백준 11724번 <연결 요소의 개수> 문제 풀이

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

n, m = map(int, input().split())
graph = [[]*(n+1) for _ in range(n+1)]
visited = [False] * (n+1)
visited[0] = True

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

def dfs(num):
  for i in graph[num]:
    if visited[i] == False:
      visited[i] = True
      dfs(i)

check = 0
for i in range(1, n+1):
  if visited[i] == False:
    check += 1
    visited[i] = True
    dfs(i)

print(check)

 

 

재귀를 이용한 DFS 알고리즘으로 문제를 풀었다. graph에 연결 요소 정보를 입력받을 때 저장시켜 준 후에 visited가 False 인 노드를 모두 방문하여 해당 노드와 한번에 연결된 요소들을 모두 체크하도록 했다.

 

 

 

다른 풀이

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)

전체적으로 비슷하긴 하지만, visited 를 False → True 바꿔주는 시점이 다르고 연결 요소의 개수를 세는 방법이 다르다.

한 가지 배운 점은, 코드에 주석을 다는 법?! 정말 코드 분석이 안 되는 분께 많은 도움이 되지 않을까 라는 생각을 했다. 알고리즘 문제 푸는 게 조금 더 익숙해지고 여유가 생긴다면 나도 도전해봐야겠다.

 

 

import sys
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        if not visited[e]:
            dfs(e)
            
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
count = 0

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    
for j in range(1, N + 1):
    if not visited[j]:
        dfs(j)
        count += 1

print(count)

 

이건 또 다른 풀이다. 마찬가지로, visited 를 False → True 바꿔주는 시점이 다르다. 해당 코드를 dfs 함수 안에 넣는 것이 확실히 더 깔끔하고 적절한 맥락 같다. 이 외의 코드는 비슷하다.

 

 

노션에 정리하는 습관을 (오늘부터) 시도해보고 있는데 꽤나 좋은 것 같다. 블로그에 옮기며 한 번 더 공부하기에도 훨씬 좋다!