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

noeliden1님의 프로필 이미지
noeliden1

작성한 질문수

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

촌수계산 (백준 2644)

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

해결된 질문

작성

·

156

1

선생님 안녕하세요!

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

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

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

감사합니다!

 

 

답변 1

2

안녕하세요 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
질문자

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

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

선생님 최고~~

 

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

noeliden1님의 프로필 이미지
noeliden1

작성한 질문수

질문하기