-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
촌수 계산
24.03.29 14:00 작성 조회수 85
1
count라는 매개변수를 같이 전달해주기 보다 dfs가 호출될 때마다 answer를 넣어주는 방식으로 풀어봤는데 왜인지 end 값을 찾았을 때 return이 적용이 안되는 거 같습니다. 혹시 어떤 문제가 있는지 봐주실 수 있나요?
import java.util.*;
import java.io.*;
class Main {
static int N, start, end, M;
static boolean[] visited;
static ArrayList<Integer>[] 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();
}
}
답변을 작성해보세요.
1
김학준
질문자2024.03.31
강의에서 나온대로 수정했지만 한 가지 의문이 있습니다. idx가 end와 같은 경우 answer의 값이 count로 초기화되고 return되는데 이때도 dfs는 재귀함수로 호출되기 때문에 이 재귀 호출이 전부 종료 되는 것이 아니라 바로 직전 단계로 올라가는 건가요?
1
개발자로 취직하기
지식공유자2024.03.29
김학준님 안녕하세요 🙂
강의를 열심히 들어주셔서 감사합니다!!
제가 질문을 이해한 건 "왜 return을 했지만 기대한대로 함수 동작이 종료가 안 되지?" 라는 건데 맞을까요?
만약 맞다면, 재귀 함수로 호출이 되다보니 return 이 불린다고 하더라도 이 재귀 호출이 전부 종료되는 것이 아니라 바로 직전 단계로 올라가기만 합니다. 그런 뒤에, 원래 하던 동작을 계속 반복할 것이기 때문에, 만약 재귀 함수를 완전히 종료하고 싶다면 차라리 별도 flag 변수를 만들어서 flag == true 이면 더 이상 함수 동작을 하지 않도록 수정이 필요해보여요!
제가 잘못 이해한 거면 다시 알려주세요!
감사합니다 🙂
김학준
질문자2024.03.30
네 제가 질문드린 의도가 맞습니다! 그래서 flag 반영해서 다시 고쳐봤는데 아직도 작동을 안 하는 거 같아 혹시 어떻게 고처야 맞는 걸까요?
import java.util.*;
import java.io.*;
class Main {
static int N, start, end, M;
static boolean[] visited;
static ArrayList<Integer>[] graph;
static int answer = -1;
static boolean flag = true;
private static void dfs(int i) {
if (i == end)
flag = false;
visited[i] = true;
if (flag) {
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();
}
}개발자로 취직하기
지식공유자2024.03.30
김학준님 안녕하세요!
아마 수정한다면 다음과 같이 수정할 것 같아요! (여기만 추가 라고 주석으로 표시한 한줄만 추가 했습니다!
import java.util.*;
import java.io.*;
class Main {
static int N, start, end, M;
static boolean[] visited;
static ArrayList<Integer>[] graph;
static int answer = -1;
static boolean flag = true;
private static void dfs(int i) {
if (i == end)
flag = false;
visited[i] = true;
if (flag) {
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);
if(flag == false) return; // 여기만 추가
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 변수는 '방문한 노드의 개수'를 세고 있는데, 저희가 원하는 건 방문한 노드의 개수가 아니라 처음 노드부터 현재 노드까지의 거리이기 때문입니다!
그래서 위와 같이 탈출 코드를 추가하면 return은 잘 되겠지만, 이게 answer가 정답이 된다는 보장이 안될 수 있으니, 학습용으로 코드를 돌려보시고 강의에서 나왔던 방식대로 수정하는 것이 가장 좋을 것 같습니다!
0
인프런 AI 인턴
2024.03.29
안녕하세요, 인프런 AI 인턴입니다.
김학준님의 질문에 대해, ‘촌수계산’과 유사한 문제를 질문하신 다른 학습자의 경우를 참고할 수 있을 것 같습니다. 해당 내용은 촌수 계산 알고리즘에 관련된 것으로 보입니다. 질문하신 부분에서 dfs가 호출될 때마다 answer를 증가시키는 로직이 문제 해결에 있어서 어려움을 겪고 있는 것으로 보입니다.
질문자분이 겪고 계신 문제는 dfs 함수 내에서 end 값을 발견했을 때 return이 제대로 동작하지 않아서 발생하는 것 같습니다. 이는 dfs 함수가 목표 노드를 찾더라도 계속해서 불필요한 탐색을 진행하고, 그 과정에서 answer 값이 예상치 못하게 증가하게 되어 발생할 수 있습니다.
촌수계산질문 링크에서는 dfs 호출 시 count를 매개변수로 전달하거나 변수 값을 증가시키는 다른 방법에 대해 설명하고 있습니다. 본질적으로 dfs 함수의 사용 방식이나 변수의 업데이트 방식에 대한 근본적인 이해가 필요해 보입니다.
촌수계산질문에서 논의된 주제는 dfs 메소드 사용과 관련 있으며, 특히 ++count와 count+1의 사용에 대한 차이점을 설명합니다. 이를 통해 김학준님의 경우에서도 dfs 탐색 로직과 answer 증가 방식에 대한 심도 있는 이해를 돕고, 문제를 해결하는 데 도움이 될 수 있을 것입니다.
이해를 돕기 위한 핵심 포인트는 dfs를 재귀적으로 호출할 때마다 count 혹은 answer 이 정확히 어떻게 업데이트 되어야 하는지 명확하게 이해하고 구현하는 것입니다. 특히 각 노드 방문 시 answer를 증가시키는 방식이 아니라 목적지에 도달했을 때만 특정 액션이 수행되도록 로직을 조정해야 할 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 3