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

noeliden1님의 프로필 이미지

작성한 질문수

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

촌수계산 (백준 2644)

2644 촌수계산 문제에 관한 질문

해결된 질문

23.10.20 13:09 작성

·

147

1

선생님 안녕하세요!

강의 너무 잘 듣고 있습니다!

제가 2644번 문제를 혼자 아래 코드로 풀어보았는데
저는 선생님께서 count변수를 dfs 함수 인자에 준 것과는 다르게 처음부터 전역변수로 설정해서 조건이 맞으면 count 변수를 1씩 증가시키는 방향으로 작성을 했는데요.
이렇게 하니까 백준에서는 틀렸다고 나오더라구요.

둘 다 if문 안에서 조건이 맞으면 카운트 변수를 1씩 증가시키는건 같은거라고 생각이 드는데 (물론 다르겠지만..)
왜 카운트 변수를 인자로 넘겨줘야할까요?

감사합니다!

 

 

답변 1

2

개발자로 취직하기님의 프로필 이미지

2023. 10. 20. 14:36

안녕하세요 noeliden1님 :)

 

cnt += 1이나 cnt+1 이나 처음 재귀함수를 호출할 때는 똑같은데요, 그 다음부터는 작성하신 방식의 cnt +=1 는 count에 값이 하나씩 누적되고, cnt + 1에는 값이 누적되지 않기 때문에 동작이 달라집니다!

 

예를 들어 처음에 idx = 1, cnt = 0으로 들어왔고, 1과 연결된 요소가 2, 3, 4가 있다고 가정했을 때, 우리가 기대하는 건 각각 2, 3, 4를 호출할 때 cnt + 1 인 1이 전달되기를 기대합니다. 그런데 작성하신 방식대로 cnt 를 하면 2번을 호출할 때는 1이겠지만, 3번을 호출할 때는 2, 4번을 호출할 때는 3 이런 식으로 누적이 되어 동작이 달라질 것 같습니다.

그래서 cnt +=1 을 하고 싶으시다면 dfs 호출한 뒤에 다시 cnt -=1 을 해줘야 촌수라는 정의를 잘 유지할 것 같아요!

 

이걸 직접 디버깅 모드로 보고 싶으시다면 위 코드에서 dfs함수를 재귀호출하기 전에 if(idx == 1)이라고 조건문을 걸고, i와 cnt의 값을 확인하거나 출력해보면 잘 보일 것 같아요!

 

혹시라도 답변이 명확하지 못했으면 알려주세요! :) 오늘도 공부 화이팅입니다.

noeliden1님의 프로필 이미지
noeliden1
질문자

2023. 10. 20. 14:42

맙소사 당신은 천재입니까?
제가 정말 초보 같은 실수를 했군요 (초보 맞음)..

명확한 답변 주셔서 감사합니다! 방금 알림 울리자마자 답변 보고 선생님 말씀처럼 cnt-=1 하니까
제대로 동작하네요.

선생님 최고~~

 

개발자로 취직하기님의 프로필 이미지

2023. 10. 20. 14:44

오 빠르시네요!! 최고 선생님이 되도록 더 좋은 강의 많이 올리고 답변도 빨리빨리 달겠습니다 :) 감사합니다!