글 읽기 - 파이썬 - 재귀에러 ㅠㅠ 고치고싶어요

cocojeun 2년 전 0

그래프가 아니라서 헤맸네요

답은 나오는데 비효율적으로 구현한것 같습니다 ㅠ

(다시 확인하니 pypy3으로 돌려도 틀렸다고하네요 헉)

혹시 어느부분이 틀렸을까요?,,ㅠ

#입력: 노드 m, 간선 n
#연결된애들
def dfs(x):
    if visited[x] ==False:
        visited[x] = True
        # print(x)
        for i in range(line):
            if x==graph[i][0]:
                dfs(graph[i][1])
            elif x==graph[i][1]:
                dfs(graph[i][0])
            else:
                continue
        return True
    return False

node, line =map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(line)]
visited = [False]*(node+1)
num=0
for i in range(1,node):
    if dfs(i) ==True:
        num+=1

print(num)

jun2korea 2년 전 1

21번 줄, range(1, node)를 하면 1번 점에서 node - 1번 점까지 확인하는데, 만약 node번 점이스스로 연결요소이면 틀리겠죠.

range(1, node + 1)로 고치면 될 것 같습니다.

그리고 graph의 모든 선분을 다 탐색하는것보다,연결선분 리스트로 만들어 탐색하는게 더 좋을거 같아요

node, line =map(int,input().split())
# graph의 i번째 리스트는 i번 점과 인접한 점
graph = [[] for _ in range(noed + 1)]
for _ in range(line):
    a, b = map(input().split())
    graph[a].append(b)
    graph[b].appned(a)

cocojeun 2년 전 0

@jun2korea 구현방법까지 친절하게 감사합니다 ! 안그래도 그래프만들어서 탐색해봤어요 훨씬 빠르네요!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 - 재귀에러 ㅠㅠ 고치고싶어요

cocojeun 2년 전 0

jun2korea 2년 전 1

cocojeun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말