연결요소개수 - 파이썬 풀이 공유

Question

안녕하세요 저는 강사님 강의로 공부하고 파이썬으로 코테를 준비하고 있습니다. 저와 같은 상황에 계신분들과 공유하고 싶어 글을 올립니다. 파이썬 풀이에서 부족한 부분 알려주시면 수정하겠습니다.~

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, sys.stdin.readline().split())
MAX = 1000 + 10
graph = [[False for  in range(MAX)] for  in range(MAX)]
visited = [False for  in range(MAX)]

for  in range(M):
x, y = map(int, sys.stdin.readline().split())
graph[x][y] = True
 graph[y][x] = True


def dfs(idx):
visited[idx] = True
 for j in range(1, N + 1):
if not visited[j] and graph[idx][j]:
dfs(j)


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

print(cnt)

개발자로 취직하기 · Answer

이렇게 파이썬 코드 공유해주셔서 정말 감사합니다!! ㅎㅎ 주말에도 이렇게 공부하시니 꼭 좋은 결과 있을 겁니다!! 참고로 제 코드도 공유 드릴게요 ㅎㅎ 작성하신 방식과 거의 동일한 것 같아요   import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # 재귀함수 (DFS) def dfs(idx): global visited, graph visited[idx] = True for i in range(1, N+1): if not visited[i] and graph[idx][i]: dfs(i) # 0. 입력 및 초기화 MAX = 1000 + 10 N, M = map(int, input().split()) graph = [[False] * MAX for _ in range(MAX)] visited = [False] * MAX answer = 0 # 1. graph에 연결 정보 채우기 for _ in range(M): u, v = map(int, input().split()) graph[u][v] = True graph[v][u] = True # 2. DFS 호출 for i in range(1, N+1): if not visited[i]: answer += 1 dfs(i) # 3. 출력 print(answer)