2644문제(촌수 구하기) 질문입니다.

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

촌수계산 (백준 2644)

해결된 질문

작성

141

1) 이 문제는 2차월 배열에 False로 초기화한다음 입력받은값만 True로 썼는데

이 문제도 메모리 낭비를 위해 빈 리스트에 넣어서 풀려면 어떻게 해야 할까요??

2) 재귀(1)중간에 재귀(2)타고 여기서 재귀(3)타고 재귀(4)타서 값을 찾았을때 리턴을 했는데요

리턴을 했다고 해서 1,2,3번의 반복문을 break하는건 아니더라고요

어짜피 답은 찾았으니 시간낭비 방지를 위해 반복문을 돌지 않는방법이 있나요?

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

답변 2

개발자로 취직하기

지식공유자

안녕하세요 먹는샘물님! 질문들 아래에 답변 남길게요 :)

1) 이 문제는 2차월 배열에 False로 초기화한다음 입력받은값만 True로 썼는데 이 문제도 메모리 낭비를 위해 빈 리스트에 넣어서 풀려면 어떻게 해야 할까요??

-> 네 가능합니다! 기존 문제들과 동일하게 2차원 배열이 아니라 list에 현재 노드와 연결되어 있는 노드들의 번호를 추가하고, 각 노드와 연결된 번호들만 찾아가면 동일하게 가능합니다! 그래서 2차원 배열로 풀었던 문제는 모두 리스트로도 구현 가능하다고 이해하시면 될 것 같습니다!

2) 재귀(1)중간에 재귀(2)타고 여기서 재귀(3)타고 재귀(4)타서 값을 찾았을때 리턴을 했는데요 리턴을 했다고 해서 1,2,3번의 반복문을 break하는건 아니더라고요. 어짜피 답은 찾았으니 시간낭비 방지를 위해 반복문을 돌지 않는방법이 있나요?

-> 가지치기라고 부르는 개념이 있어서, 재귀 함수 중간에 특정 조건이 만족 되면 break하거나 return해서 이전 호출로 돌아가도록 구현할 수도 있습니다. 그런데 이 방식은 문제마다 가능할 수도 있고 아닐 수도 있기 때문에 처음 공부하실 때는 약간은 비효율적이지만 정형화된 틀로 공부해두시는 것이 더 쉬울 것 같아요. 이래야 어떤 유형의 DFS가 나와도 공통적으로 적용하고 구현하기 쉬울 것 같고, 해보시면서 중간에 조건에 따라 탈출하는 코드를 작성하시는 것도 좋은데, 사실 visited 배열을 통해서 이미 방문한 노드는 방문하지 않고 있기 때문에, 반복문을 몇번 더 수행하는 것은 성능에 큰 영향을 주지는 않습니다! 그래서 정리하자면 가능하지만 특화된 코드를 짜야하는 부담이 크고, 그것에 비해 얻는 성능 개선은 큰 차이가 없어서 추천 드리진 않습니다 🙂

혹시 더 궁금하신 부분 있으면 댓글 남겨주세요!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

먹는샘물님의 문제에 관련하여, 2차원 배열을 사용하지 않고 리스트를 이용해 효율적으로 문제를 해결하는 방법에 대해 질문해주신 것으로 보입니다. 질문 1)에 대해서는, 대개 인접 리스트(Adjacency List)라는 데이터 구조를 통해 그래프를 표현할 수 있습니다. 인접 리스트는 각 노드에 연결된 노드의 리스트를 저장하는 방식으로, 메모리를 효율적으로 사용하면서 그래프를 표현할 수 있습니다.

2)에 대한 질문에서는 “재귀 함수”를 사용할 때 특정 조건을 만족하면 반복문을 즉시 종료하고 결과 값을 반환하는 방법에 대해 물으신 것 같습니다. 재귀 함수에서 조건을 만족했을 때 그 이후의 모든 재귀 호출을 중지하려면 반환 값(return value)을 적절하게 활용해야 합니다. 각 재귀 함수 사이에서 반환 값을 체크하고, 특정 조건이 만족되었음을 나타내는 신호를 함수를 호출한 상위 함수에게 전달할 수 있습니다.

그럼에도 불구하고 직접 관련된 답변을 찾지 못했습니다. 그러나 모범 답안을 제시하는 것이 아니며 아래의 유사 질문들을 참고하는 것이 도움이 될 수 있습니다:

촌수계산 문제 질문
이 링크에서는 촌수 계산과 관련된 DFS 질문에 대한 답변을 볼 수 있습니다. 전역 변수와 매개변수를 이용한 차이를 설명하고 있어, 질문 2)에 관련된 어느 정도 해결책이 될 수 있습니다.
2644 촌수계산 문제에 관한 질문
이 링크에서는 count 변수를 전역 변수로 설정했을 때와 매개변수로 넘겼을 때의 차이를 설명하고 있습니다.

추가로 궁금한 점이 있으시면, 강의 내 Q&A 섹션을 통해 질문하시면 강의를 담당하고 계신 지식공유자께서 보다 자세한 답변을 제공해드릴 수 있을 것 입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

먹는샘물

질문자

위에 달린 답글은 AI같군요...

위에 제가 질문한것을 스스로 짜 보았습니다.

이렇게 작성하면 백준에서 채점할떄 메모리나 수행시간이 줄어들것으로 기대했는데 그렇지는 않네요 혹시 이유를 알수 있을까요?

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def dfs(start, count):
    #print("start",start)
    global graph, visted, answer, end, finish
    visted[start] = True
    if start == end:
        #print("걸리냐?")
        answer = count
        finish = True
        #print(answer, count)
        return
    
    for i in graph[start]:
        if visted[i] == False:
            #print("start", start, "count", count)
            dfs(i, count + 1)
        elif finish == True:
            return
        else: pass#print("안탐, start, i", start, i)
            
# 1. 입력받기
finish = False
n = int(input())
start, end = map(int, (input().split()))
m = int(input())

# 2. 그래프 그리기
graph = [[] * (n+1) for _ in range(n+1)]
visted = [False] * (n+1)
answer = -1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 3. DFS 호출
dfs(start, 0)

# 4. 출력
print(answer)

개발자로 취직하기

지식공유자

우선 고민하신 걸 벌써 구현해보셨다니..!! 너무 좋습니다 ㅎㅎ 결국 직접 구현해보고 실험해보는 것이 가장 빠르게 배우는 방법인 것 같아 너무 좋아요.

큰 차이가 나지 않는 이유는 두 가지로 보여요.

1) 반복문만 몇 바퀴 더 도는 것은 크게 성능 하락을 유발하지 않습니다. 어차피 이미 방문을 했다면, visited[i] == true가 되어 재수행 되지 않아서 그냥 반복문만 헛(?)도는데, 이는 성능에 큰 영향을 미치지 않아서 '원래의 형태도 충분히 빨랐다'라고 이해하셔도 될 것 같습니다.

2) 그리고 elif finish == True가 추가되었기 때문에, finish가 빨리 발생하지 않는 경우에는 오히려 반복문 안에서 조건을 하나 더 확인하게 되는 것이고, 이러다보면 경우에 따라서는 성능이 오히려 안 좋아질 수도 있습니다. 즉, finish 변수를 봄으로써 얻는 성능 이득보다 finish 변수를 확인하면서 발생하는 조건문이 성능에 악영향을 미칠 수 있는데, 이 둘의 큰 차이가 없다 보니 성능이 비슷하게 나오는 것 같습니다.

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

2644문제(촌수 구하기) 질문입니다.