[Python] 11724번 연결 요소의 개수

✏️ 문제

 

문제 파악

처음엔 연결 요소가 뭐지 싶어서 검색해봤는데 많은 좋은 자료들이 있었다. (모르면 보고 오시길 추천!)

문제의 예제1, 예제2를 그림 그려본다면 연결 요소의 개수는 다음과 같이 된다.

처음 코드를 짤 땐 visited 배열을 1차원 배열로 줬는데 그러면 서로 연결되어 있다는 게 담기 어려웠다. (연결되어 있으면 1로 변경했을 시 1차원 배열이면 예제1의 경우 전부 1이 됨)

그래서 2차원 배열로 구현하니 쉽게 풀 수 있었다!

 

아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.

1. 재귀 함수를 사용하지 않고 스택으로 DFS 구현
2. sys.setrecursionlimit() 사용

나는 1번째 방법으로 해결했다!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

import sys
input = sys.stdin.readline

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

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

def dfs(v):
  stack = [v]
  visited[v] = 1

  while stack:
    node = stack.pop()

    for i in range(1, n+1):
      if visited[i] == 0 and graph[node][i] == 1:
        stack.append(i)
        visited[i] = 1

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

print(cnt)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS