문제
- 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단 노드 까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요.
- 각 경로의 길이는 루트도느에서 말단노드까지 가는데 디동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.
입력
- 생략
출력
- 3번 노드까지의 길이인 1
입출력 예제
- 생략
풀이방식
이번 문제는 이진트리, 재귀함수를(을) 사용하여 푸는 문제이다.
더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
설계과정
1. 해당 노드가 말단 노드임을 확인하고, 말단 노드라면 레벨 값을 바로 리턴한다.
2. 말단 노드가 아니라면 자식 노드들 중에 더 작은 레벨값을 리턴받는다.
* 주의 : DFS는 자식노드가 둘 다 있거나 아예 없을 경우에만 사용 가능하다.
* 해당 문제는 BFS로 푸는 것이 더 알맞으나, DFS 연습을 위해 해당 방식으로 풀어보았다.
풀이과정
1. NodeThree 클래스를 생성하고, 각 변수들을 선언 및 초기화한다.
- data : 각 트리의 값이 들어갈 변수이다.
- lt, rt : 각각 왼쪽과 오른쪽 노드의 값을 저장할 변수이다.
2. TreeDFS 클래스 안에 DFS 메소드를 작성한다.
3. 해당 노드가 말단 노드이면 L을 바로 리턴한다.
- lt 와 rt 가 null 이라는 것은 자식 노드가 없는 말단 노드임을 의미한다.
4. 말단 노드가 아니라면 자식 노드들 중에 더 작은 값을 가진 노드의 값을 리턴받는다.
- 자세한 설명은 아래와 같다.
1. 30번 line에서 DFS(0, tree.root) 코드를 통해 루트 노드가 만들어진다.
2. 18번 line에서 DFS(L+1, root.lt) 코드를 통해 왼쪽 자식 노드가 만들어진다.
- (a, b) : 왼쪽은 L, 오른쪽은 주소값이다.
3. 마찬가지로 재귀함수가 호출되면서 동일한 코드를 통해 왼쪽 자식 노드가 만들어진다.
4. 또 다시 재귀함수가 호출되면, if문에 걸리므로 L 값인 2를 리턴한다.
- DFS(2,400) 은 자식 노드가 없기 때문에 if문으로 넘어간다.
5. 18번 line에서 DFS(L+1, root.rt) 코드를 통해 오른쪽 자식 노드가 만들어진다.
6. 자식 노드가 없으므로 if문에 걸려서 L 값인 2를 리턴한다.
7. DFS(1,200) 노드가 가진 자식 노드들 중에 더 작은 값을 리턴받는다.
- 여기에선 동일하므로 2를 리턴받는다.
- Math.min() : 입력받은 두 개의 인자 중 작은 값을 리턴한다.
8. 18번 line에서 DFS(L+1, root.rt) 코드를 통해 오른쪽 자식 노드가 만들어진다.
9. 자식 노드가 없으므로 if문에 걸려서 L 값인 1을 리턴한다.
10. DFS(0,100) 노드가 가진 자식 노드들 중에 더 작은 값을 리턴받는다.
11. 결과적으로 1을 리턴받게 된다.
5. 루트 노드가 리턴받은 값을 출력한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
