문제
- 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단 노드 까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요.
- 각 경로의 길이는 루트도느에서 말단노드까지 가는데 디동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.
입력
- 생략
출력
- 3번 노드까지의 길이인 1
입출력 예제
- 생략
풀이방식
이번 문제는 이진트리, 재귀함수를(을) 사용하여 푸는 문제이다.
더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
설계과정
1. 맨 처음에 발견되는 말단 노드가 가장 짧은 거리에 있는 말단 노드이므로 그대로 출력한다.
2. 말단 노드가 아니라면 자식 노드들을 큐에 넣는다.
3. 레벨을 증가시키며 해당 과정을 통해 가장 짧은 거리를 출력한다.
풀이과정
1. NodeFour 클래스를 생성하고, 각 변수들을 선언 및 초기화한다.
- data : 각 트리의 값이 들어갈 변수이다.
- lt, rt : 각각 왼쪽과 오른쪽 노드의 값을 저장할 변수이다.
2. TreeBFS 클래스 안에 BFS 메소드를 작성한다.
3. Q 를 선언하고 노드 값을 넣는다.
- 이 때 레벨 즉, 거리를 의미하는 변수 L도 같이 선언하고 0으로 초기화한다.
4. Q가 비어있지 않으면 계속해서 도는 while 문을 선언한다.
5. Q의 크기를 저장하는 변수 len을 선언한다.
- len은 Q의 크기 즉, 각 레벨에 해당하는 노드의 개수를 의미한다.
6. 0부터 len까지 도는 for 문을 작성한다.
7. for문 안에서 현재의 노드를 꺼내고, 해당 노드가 말단 노드인지를 확인하여 말단 노드이면 L을 리턴한다.
8. 말단 노드가 아니라면 해당 노드들을 큐에 넣는다.
9. L을 증가시키며 탐색을 반복한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
