Recursive, Tree, Graph(DFS, BFS 기초) 3 - 이진트리, 상태트리 BFS

학습자료 : https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84#

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

문제 1 : 

아래 그림과 같은 이진트리를 레벨탐색(넓이우선탐색) 연습하세요.

레벨탐색순회 출력 : 1, 2, 3, 4, 5, 6, 7

 

풀이 :

 

소스코드 :

import java.util.*;
import java.io.*;
class Node {
	int data;
	Node lt, rt;
	public Node(int value) {
		data = value;
		lt = rt = null;
	}
}

class Main {
	Node root;
	public void BFS(Node root) {
		Queue<Node> Q = new LinkedList<>(); // Node 객체를 저장하는 Queue
		Q.offer(root); // 첫번째 노드 큐에 삽입
		int level = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();
			System.out.print(level + " : ");
			for(int i=0; i<len; i++) {
				Node curNode = Q.poll(); // current Node
				System.out.print(curNode.data + " ");
				if (curNode.lt != null) Q.offer(curNode.lt);
				if (curNode.rt != null) Q.offer(curNode.rt);
			}
			level++;
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		T.root = new Node(1);
		T.root.lt = new Node(2);
		T.root.rt = new Node(3);
		T.root.lt.lt = new Node(4);
		T.root.lt.rt = new Node(5);
		T.root.rt.lt = new Node(6);
		T.root.rt.rt = new Node(7);
		T.BFS(T.root);
	}
}

 

출력결과 :

 

 

 

문제 2 :

블로그 주인장이 다람쥐를 잃어버렸다. 다람쥐의 위치를 찾아야한다.

주인장과 다람쥐의 위치가 수직전상의 좌표 점으로 주어지고, 주인장은 움직이지 않는 다람쥐를 찾아 이동한다.

한 번 움직일 때 마다 주인장은 앞으로 1칸 or 뒤로 1칸 or 앞으로 5칸 이동한다.

최소 몇 번 움직여야 다람쥐의 위치까지 갈 수 있는지 구하는 프로그램을 작성하여라.

(직선의 좌표 점은 1부터 10,000까지이다.)

 

풀이 :

소스코드 :

import java.util.*;
class Main {
	int answer = 0;
	int[] move = {1, -1, 5};
	int[] ch; // 한번 큐에 들어간 것 중복안되게 체크하는 배열
	Queue<Integer> Q = new LinkedList<>();
	public int BFS(int s, int e) {
		ch = new int[10001];
		ch[s] = 1;
		Q.offer(s);
		int level = 0;
		while (!Q.isEmpty()) {
			int len = Q.size(); // 해당 level에 존재하는 원소의 개수
			for(int i=0; i<len; i++) {
				int x = Q.poll(); // 부모 노드
				for(int j=0; j<3; j++) {
					int nx = x + move[j]; // 자식 노드
					if (nx == e) return level + 1;
					if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
						ch[nx] = 1;
						Q.offer(nx);
					}
				}
			}
			level++;
		}
		return 0;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int e = sc.nextInt();
		System.out.println(T.BFS(s, e));
	}
}