값이 k인 트리 노드의 깊이
문제 정보
- 사이트 : 백준 알고리즘 사이트
- 문제 번호 : 25511
- 문제 분류 : dfs
- 난이도 : silver 2
문제 풀이
내가 짠 코드
생각한 문제 조건
1. n개의 정점 n-1 간선 -> 모든 노드가 하나씩 이어져있다.
2. 0~n-1의 노드 번호, 0이 root이다.
3. 간선에는 가중치가 없다.
4. 루트의 깊이는 0이고, 자식의 깊이는 부모 + 1이다.
💭 생각 노트
- n의 범위가 2이상 100,000이하 이므로 인접 행렬보단 인접 리스트를 사용하는 것이 공간적으로 좋아보였다.
- 정점의 번호와 값이 달라 class Node를 만들까 하였지만 입력 순서가 정점 번호 순과 동일해 그냥 value 배열을 만들어 index와 정점을 매칭해 처리하였다.
- dfs를 0번(루트) 부터 시작해 인접 리스트를 돌며 깊이를 우선으로 탐색하였다.
- 이때, 리스트를 돌다 방문하지 않은 점이 있으면 자식 정점이므로 깊이를 +1 해주고 dfs를 호출한다.
- 정점의 값이 k인 값을 찾으면 그때의 depth값이 해당 노드의 깊이이므로 결과로 출력하였다.
public class BJ_25511 {
static ArrayList<Integer>[] list; // 정점 간의 관계를 저장하는 리스트
static int[] value; // 정점의 값을 저장하는 배열
static boolean[] visit; // 정점의 방문 상태를 저장하는 배열
static int k; // 찾으려는 정점의 값
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
k = Integer.parseInt(input[1]);
list = new ArrayList[n];
visit = new boolean[n];
value = new int[n];
for (int i = 0; i < n; i++) {
list[i] = new ArrayList<>();
}
// 정점들의 연관관계를 인접리스트로 구현
for (int i = 0; i < n-1; i++) {
input = br.readLine().split(" ");
list[Integer.parseInt(input[0])].add(Integer.parseInt(input[1]));
}
input = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
value[i] = Integer.parseInt(input[i]);
}
dfs(0, 0);
br.close();
}
public static void dfs(int start, int depth) {
// 정점을 방문했으므로 visit를 true 변경
visit[start] = true;
// 방문한 정점의 값이 k(목표 값)과 같으면 출력
if(value[start] == k){
System.out.println(depth);
return;
}
// 인접리스트에서 방문하지 않은 정점이 있으면 자식노드 이므로 깊이를 증가시키고 방문
for (Integer integer : list[start]) {
if(!visit[integer])
dfs(integer, depth+1);
}
}
}참고할만한 다른 코드
java로 맞은 사람이 나 혼자라 다른 코드를 참고할 수 없었다.
이런 경험은 처음해봐서 당황스럽고 뿌듯했다 :)
