촌수 계산

Question

count라는 매개변수를 같이 전달해주기 보다 dfs가 호출될 때마다 answer를 넣어주는 방식으로 풀어봤는데 왜인지 end 값을 찾았을 때 return이 적용이 안되는 거 같습니다. 혹시 어떤 문제가 있는지 봐주실 수 있나요? import java.util.*; import java.io.*; class Main { static int N, start, end, M; static boolean[] visited; static ArrayList[] graph; static int answer = -1; private static void dfs(int i) { if (i == end) { System.out.println("end: " + end); return; } visited[i] = true; for (int j = 0; j < graph[i].size(); j++) { int next = graph[i].get(j); if (visited[next] == false) { System.out.println("next: " + next); dfs(next); answer++; } } } public static void main(String[] args) throws IOException{ // 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); N = Integer.parseInt(br.readLine()); // 노드의 개수 StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); // 시작 노드 end = Integer.parseInt(st.nextToken()); // 끝 노드 System.out.println(end); M = Integer.parseInt(br.readLine()); // 간선의 개수 visited = new boolean[N+1]; // graph 선언 후 초기화 graph = new ArrayList[N+1]; for (int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); } for (int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } System.out.println(Arrays.toString(graph)); // dfs 호출 dfs(start); System.out.println(answer); bw.close(); br.close(); } }

김학준 · Answer

강의에서 나온대로 수정했지만 한 가지 의문이 있습니다. idx가 end와 같은 경우 answer의 값이 count로 초기화되고 return되는데 이때도 dfs는 재귀함수로 호출되기 때문에 이 재귀 호출이 전부 종료 되는 것이 아니라 바로 직전 단계로 올라가는 건가요?

개발자로 취직하기 · Answer

김학준님 안녕하세요 🙂 강의를 열심히 들어주셔서 감사합니다!! 제가 질문을 이해한 건 "왜 return을 했지만 기대한대로 함수 동작이 종료가 안 되지?" 라는 건데 맞을까요? 만약 맞다면, 재귀 함수로 호출이 되다보니 return 이 불린다고 하더라도 이 재귀 호출이 전부 종료되는 것이 아니라 바로 직전 단계로 올라가기만 합니다. 그런 뒤에, 원래 하던 동작을 계속 반복할 것이기 때문에, 만약 재귀 함수를 완전히 종료하고 싶다면 차라리 별도 flag 변수를 만들어서 flag == true 이면 더 이상 함수 동작을 하지 않도록 수정이 필요해보여요! 제가 잘못 이해한 거면 다시 알려주세요!   감사합니다 🙂

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 김학준님의 질문에 대해, &lsquo;촌수계산&rsquo;과 유사한 문제를 질문하신 다른 학습자의 경우를 참고할 수 있을 것 같습니다. 해당 내용은 촌수 계산 알고리즘 에 관련된 것으로 보입니다. 질문하신 부분에서 dfs 가 호출될 때마다 answer 를 증가시키는 로직이 문제 해결에 있어서 어려움을 겪고 있는 것으로 보입니다. 질문자분이 겪고 계신 문제는 dfs 함수 내에서 end 값을 발견했을 때 return 이 제대로 동작하지 않아서 발생하는 것 같습니다. 이는 dfs 함수가 목표 노드를 찾더라도 계속해서 불필요한 탐색을 진행하고, 그 과정에서 answer 값이 예상치 못하게 증가하게 되어 발생할 수 있습니다. 촌수계산질문 링크에서는 dfs 호출 시 count 를 매개변수로 전달하거나 변수 값을 증가시키는 다른 방법에 대해 설명하고 있습니다. 본질적으로 dfs 함수의 사용 방식이나 변수의 업데이트 방식에 대한 근본적인 이해가 필요해 보입니다. 촌수계산질문 에서 논의된 주제는 dfs 메소드 사용과 관련 있으며, 특히 ++count 와 count+1 의 사용에 대한 차이점을 설명합니다. 이를 통해 김학준님의 경우에서도 dfs 탐색 로직과 answer 증가 방식에 대한 심도 있는 이해를 돕고, 문제를 해결하는 데 도움이 될 수 있을 것입니다. 이해를 돕기 위한 핵심 포인트는 dfs 를 재귀적으로 호출할 때마다 count 혹은 answer 이 정확히 어떻게 업데이트 되어야 하는지 명확하게 이해하고 구현하는 것입니다. 특히 각 노드 방문 시 answer 를 증가시키는 방식이 아니라 목적지에 도달했을 때만 특정 액션이 수행되도록 로직을 조정해야 할 수 있습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.