백준 11724 연결 요소의 개수 문제

[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편

연결 요소의 개수 (백준 11724)

해결된 질문

작성

337

선생님 안녕하세요

일단 너무 만족스러운 강의 준비해주셔서 감사하고 정말 돈이 하나도 아깝지 않은 강의입니다. DFS 강의 말고도 다른 알고리즘 강의도 준비해주시면 너무 좋을것 같아요 ㅠㅠ

아무튼 질문은요,

선생님 강의를 듣고 아래처럼 제가 코드를 짰는데
선생님 코드랑 몇번을 비교해도 다른 점이 보이질 않는데 백준에서 제출했을 때 계속 메모리 초과라고 나옵니다.

혹시나 제가 바보같은 실수를 했을 수 있으니 미리 사과드립니다 ㅠㅠ!!

감사합니다

import sys

sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())

MAX = 1000 + 10

graph = [[False] * MAX for _ in range(MAX)]
visited = [False] * MAX
answer = 0

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


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


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

print(answer)

python 코딩-테스트 알고리즘 dfs python3

답변 2

개발자로 취직하기

지식공유자

noeliden1님 안녕하세요 :)

도움되신다니 너무 다행이에요 ㅠ 얼른 다른 강의들도 만들어볼게요!

위 코드 보고 백준에 그대로 제출했는데 저는 정답이 나오더라고요. 혹시 백준에서 언어는 어떤 걸로 설정하셨나요? 세부사항 알려주시면 저도 똑같이 만들어놓고 더 볼 수 있을 것 같아요 ㅎㅎ

코드만 보고 확인했을 때 아마 setrecursion을 지운다고 통과가 되진 않을 것 같은데 그 부분도 특이하네요. 제 생각에 가장 의심 되는 건 dfs 함수 내에서 global로 선언하는 부분이 제외됐다는 거였어요. 우선 저도 똑같은 상황을 만들 수 있으면 만들어놓고 확인해볼게요!

감사합니다 :)

noeliden1

질문자

제일 위에 sys.setrecursionlimit(10**6)을 지우니까 통과했습니다!

개발자로 취직하기

지식공유자

noeliden1님 안녕하세요 :)

도움되신다니 너무 다행이에요 ㅠ 얼른 다른 강의들도 만들어볼게요!

감사합니다 :)

noeliden1

질문자

저는 pypy3 언어로 설정해놓고 제출했습니다! 저도 왜 통과가 안됐는지 의문이에요 ㅠㅠ. 그것과 별개로 정말 훌륭한 강의 감사합니다! 이렇게 같은 수업 방식으로 다른 알고리즘 강의가 있으면 다 결제해서 듣고 싶습니다 정말 많이 배울것 같아요! 감사합니다

개발자로 취직하기

지식공유자

아 PyPy3로 제출하셔서 메모리 초과가 발생한 것 같아요! 저도 자세하게 공부해본 적은 없지만, PyPy3와 Python 내부 동작이 꽤 달라서 PyPy3는 조금 더 빠른 대신 메모리 효율이 많이 떨어진다고 알고 있어요! 그렇다보니 메모리 사용이 많은 DFS나 재귀에서는 PyPy3가 취약한 것 같아요.

해결책은 크게 2가지인 것 같아요!

setrecursionlimit(10**5)로 수정 : setrecursionlimit은 "이 만큼의 재귀 호출을 감당할 수 있도록 미리 메모리를 할당해주는 동작이다"라고 이해하시면 될 것 같아요. 그리고 PyPy3에서 감당 가능한 숫자를 적당히 찾아서 써야할 것 같은데 우선 이 문제에서는 10**5면 같은 코드로 통과가 됩니다! 다른 문제에서도 메모리 초과가 발생하면 이렇게 바꿔갈 수 있을 것 같아요.
Python3 사용하기 : 조금 더 근본적인 해결책은 Python3를 사용하는 것일 것 같아요! 혹시 Pypy3를 써야만 하는 이유가 있다면 또 고려가 필요하겠지만요 ㅎㅎ

noeliden1

질문자

너무 친절하게 답변 주셔서 감사합니다 선생님! 앞으로 Python3로 언어를 설정해놓고 문제를 풀어야겠어요 ㅎㅎ! 남은 강의 열심히 듣고 또 중간에 질문 있으면 찾아봴게요! 감사합니다

인프런 커뮤니티 질문&답변

백준 11724 연결 요소의 개수 문제