-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
연결요소개수 - 파이썬 풀이 공유
23.08.26 11:32 작성 조회수 207
1
안녕하세요 저는 강사님 강의로 공부하고 파이썬으로 코테를 준비하고 있습니다. 저와 같은 상황에 계신분들과 공유하고 싶어 글을 올립니다. 파이썬 풀이에서 부족한 부분 알려주시면 수정하겠습니다.~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)
답변을 작성해보세요.
1
개발자로 취직하기
지식공유자2023.08.26
이렇게 파이썬 코드 공유해주셔서 정말 감사합니다!! ㅎㅎ
주말에도 이렇게 공부하시니 꼭 좋은 결과 있을 겁니다!!
참고로 제 코드도 공유 드릴게요 ㅎㅎ 작성하신 방식과 거의 동일한 것 같아요
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)
답변 1