문제 : https://www.acmicpc.net/problem/2644
- Q) 가족 관계도 기준 촌수 구하기
- 나와 다른 가족과의 촌수는?
제한 조건
1) N(사람수) <= 100
2) 첫번째 가족 번호(촌수=0), 두번째 가족번호(촌수=?)
🚨오늘의 학습
⭐️DFS⭐️
- 두사람간의 관계를 그래프 탐색으로 구현 가능하다
- 특정 노드(사람)에서 시작하여 다른 노드(사람)로의 연결 경로를 찾는 데 효과적이다
🗝️ 가족 관계 그래프로 구현하기
🗝️ 재귀함수로 연결된 가족의 더 깊은 관계 탐색하기
🗝️ 재방문 방지를 위해 방문 여부 확인✅ & 방문했다면 방문하지 않기
import java.io.*;
import java.util.*;
public class Family_korean {
static int[] visited;
static int edge = 0;
static int node = 0;
static int startNode = 0;
static int endNode = 0;
static int[][] graph ;
static int step = -1;
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
startNode = Integer.parseInt(st.nextToken());
endNode = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
edge = Integer.parseInt(st.nextToken());
graph = new int[node+1][node+1];
visited = new int[node+1];
for(int i=0; i<edge; i++){
st = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
graph[node1][node2] = 1;
graph[node2][node1] = 1;
}
dfs(startNode,0);
System.out.println(step);
}
public static void dfs(int node, int chone){
System.out.println("dfs: "+node+" , "+chone);
visited[node]=1;
if(node==endNode){
System.out.println("endNode : "+node);
step = chone;
return;
}
for(int j=0; j<graph[node].length;j++){
if(graph[node][j]==1 && visited[j]!=1){
System.out.println("for: "+node+" , "+j);
dfs(j,chone+1);
}
}
}
}
오늘의 회고
DFS가 어떤 경우 사용되어야 하는지는 조금은 알것(?) 같은 느낌이다(느낌만)
그런데 어떻게 재귀로 구현 하는지가 어렵다ㅜㅜ 재귀함수가 어려운거 같다
문제를 풀면서 익숙해지는 시간이 필요할듯 하다
재귀 함수 동작을 정확하게 이해하기 위해서 중간중간 출력해보며 확인해 보았다
재귀함수
- 재귀 함수는 호출된 순서대로 동작하며, 각 호출(메서드)이 스택 형태로 쌓여서 마지막에 호출된 함수부터 종료됩니다.
- 가장 깊은 호출(즉, 더 깊은 dfs 호출로 들어가지 않는 호출)이 먼저 실행을 마친 뒤에 호출된 순서의 역순으로 이전 함수들이 실행을 마치고 돌아옵니다.
with me