본문 바로가기
알고리즘/JAVA

Recursive, Tree, Graph(DFS, BFS 기초)

by vivi 2021. 9. 26.

1. 재귀함수(스택프레임)

import java.util.*;

class Main {
	public void DFS(int n) {
		if (n == 0)
			return;
		else {
			DFS(n - 1);
			System.out.print(n + " ");
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		T.DFS(kb.nextInt());
		kb.close();
	}
}

2.이진수 출력(재귀)

import java.util.*;

class Main {
	public void DFS(int n) {
		if (n == 0)
			return;
		else {
			DFS(n / 2);
			System.out.print(n % 2);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		T.DFS(kb.nextInt());
		kb.close();
	}
}

3.팩토리얼

import java.util.*;

class Main {
	public int DFS(int n) {
		if (n == 1)
			return 1;
		else {
			return n * DFS(n - 1);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		System.out.print(T.DFS(kb.nextInt()));
		kb.close();
	}
}

4.피보나치 재귀(메모이제이션)

import java.util.*;

class Main {
	static int[] arr;

	public int DFS(int n) {
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 1;
		if (arr[n] != 0)
			return arr[n];
		else {
			return arr[n] = DFS(n - 1) + DFS(n - 2);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		arr = new int[n + 1];
		T.DFS(n);
		for (int x : arr)
			System.out.print(x + " ");
		kb.close();
	}
}

 

import java.util.*;

class Main {
	static int[] fibo;

	public int DFS(int n) {
		if (fibo[n] > 0)
			return fibo[n];
		if (n == 1)
			return fibo[n] = 1;
		else if (n == 2)
			return fibo[n] = 1;
		else
			return fibo[n] = DFS(n - 2) + DFS(n - 1);
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		fibo = new int[n + 1];
		T.DFS(n);
		for (int i = 1; i <= n; i++)
			System.out.print(fibo[i] + " ");
		kb.close();
	}
}

 

import java.util.*;

class Main {
	static int[] fibo;

	public void DFS(int n) {
		fibo[0] = 0;
		fibo[1] = 1;
		fibo[2] = 1;
		for (int i = 3; i <= n; i++)
			fibo[i] = fibo[i - 2] + fibo[i - 1];
		return;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		fibo = new int[n + 1];
		T.DFS(n);
		for (int i = 1; i <= n; i++)
			System.out.print(fibo[i] + " ");
		kb.close();
	}
}

5. 이진트리순회(DFS : Depth-First Search)

 

 

전위순회 - 부모 왼쪽 자식 오른쪽 자식

중위순회 - 왼쪽 자식 부모 오른쪽 자식

후위순회 - 왼쪽 자식 오른쪽 자식 부모

 

 

import java.util.*;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;

	public void DFS(Node root) {
		if (root == null)
			return;
		else {
			System.out.print(root.data + " ");
			DFS(root.lt);
			DFS(root.rt);
		}
	}

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

결과 : 1 2 4 5 3 6 7

 

import java.util.*;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;

	public void DFS(Node root) {
		if (root == null)
			return;
		else {
			DFS(root.lt);
			System.out.print(root.data + " ");
			DFS(root.rt);
		}
	}

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

결과 : 4 2 5 1 6 3 7

 

import java.util.*;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;

	public void DFS(Node root) {
		if (root == null)
			return;
		else {
			DFS(root.lt);
			DFS(root.rt);
			System.out.print(root.data + " ");
		}
	}

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

결과 : 4 5 2 6 7 3 1

 

6. 부분집합 구하기(DFS)

import java.util.*;

class Main {
	static int n;
	static int[] ch;

	public void DFS(int L) {
		if (L == n + 1) {
			for (int i = 0; i < n + 1; i++)
				if (ch[i] == 1)
					System.out.print(i + " ");
			System.out.println();
		} else {
			ch[L] = 1;
			DFS(L + 1);
			ch[L] = 0;
			DFS(L + 1);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		n = 3;
		ch = new int[n + 1];
		T.DFS(1);
	}
}

 

7. 이진트리 레벨탐색(BFS : Breadth-First Search)

import java.util.*;

class Node {
	int data;
	Node lt;
	Node rt;

	public Node(int val) {
		this.data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;

	public void BFS(Node root) {
		Queue<Node> Q = new LinkedList<>();
		Q.offer(root);
		int L = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();
			System.out.print(L + " : ");
			for (int i = 0; i < len; i++) {
				Node cur = Q.poll();
				System.out.print(cur.data + " ");
				if (cur.lt != null)
					Q.offer(cur.lt);
				if (cur.rt != null)
					Q.offer(cur.rt);
			}
			L++;
			System.out.println();
		}
	}

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

 

8. 송아지 찾기 1(BFS : 상태트리탐색)

 

import java.util.*;

class Node {
	int data;
	Node lt;
	Node mid;
	Node rt;

	public Node(int val) {
		this.data = val;
		lt = mid = rt = null;
	}
}

class Main {
	Node root;

	public int BFS(int S, int E) {
		Queue<Node> Q = new LinkedList<>();
		root = new Node(S);
		Q.offer(root);
		int L = Math.abs((E - S) / 5);
		if (S <= E) {
			S = 0;
			E = (E - S) - L * 5;
		} else {
			return L = S - E;
		}
		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Node cur = Q.poll();
				if (cur.data == E)
					return L;
				else {
					if (cur.data < E) {
						cur.lt = new Node(cur.data + 1);
						cur.rt = new Node(cur.data + 5);
					}
					if (cur.data > E) {
						cur.mid = new Node(cur.data - 1);
					}
					if (cur.lt != null)
						Q.offer(cur.lt);
					if (cur.mid != null)
						Q.offer(cur.mid);
					if (cur.rt != null)
						Q.offer(cur.rt);
				}
			}
			L++;
		}
		return L;
	}

	public static void main(String[] args) {
		Main tree = new Main();
		Scanner kb = new Scanner(System.in);
		int S = kb.nextInt();
		int E = kb.nextInt();
		System.out.print(tree.BFS(S, E));
	}
}

O(3^n)...????

 

import java.util.*;

class Main {
	int answer = 0;
	int[] dis = { 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 L = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				int x = Q.poll();
				for (int j = 0; j < 3; j++) {
					int nx = x + dis[j];
					if (nx == E)
						return L + 1;
					if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
						Q.offer(nx);
						ch[nx] = 1;
					}
				}
			}
			L++;
		}
		return L;
	}

	public static void main(String[] args) {
		Main tree = new Main();
		Scanner kb = new Scanner(System.in);
		int S = kb.nextInt();
		int E = kb.nextInt();
		System.out.print(tree.BFS(S, E));
	}
}

 

9. Tree 말단노드까지의 까장 짧은 경로(DFS)

import java.util.*;

class Node {
	int data;

	Node lt;
	Node rt;

	public Node(int val) {
		this.data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;
	int min = Integer.MAX_VALUE;

	public int DFS(Node cur, int L) {
		if (cur.lt == null && cur.rt == null)
			return L;
		else {
			if (cur.lt != null)
				min = Math.min(DFS(cur.lt, L + 1), min);
			if (cur.rt != null)
				min = Math.min(DFS(cur.rt, L + 1), min);
		}
		return min;
	}

	public static void main(String[] args) {
		Main tree = new Main();
		tree.root = new Node(1);
		tree.root.lt = new Node(2);
		tree.root.rt = new Node(3);
		tree.root.rt.lt = new Node(6);
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		System.out.print(tree.DFS(tree.root, 0));
	}
}

 

import java.util.*;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		this.data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;

	public int DFS(Node cur, int L) {
		if (cur.lt == null && cur.rt == null)
			return L;
		else
			return Math.min(DFS(cur.lt, L + 1), DFS(cur.rt, L + 1));
	}

	public static void main(String[] args) {
		Main tree = new Main();
		tree.root = new Node(1);
		tree.root.lt = new Node(2);
		tree.root.rt = new Node(3);
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		System.out.print(tree.DFS(tree.root, 0));
	}
}

 

10. Tree 말단노드까지의 까장 짧은 경로(BFS), 레벨 탐색

import java.util.*;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		this.data = val;
		lt = rt = null;
	}
}

class Main {
	Node root;
	Queue<Node> Q = new LinkedList<>();

	public int BFS(Node root) {
		Q.offer(root);
		int L = 0;
		Node cur;
		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				cur = Q.poll();
				if (cur.lt == null && cur.rt == null)
					return L;
				else {
					if (cur.lt != null)
						Q.offer(cur.lt);
					if (cur.rt != null)
						Q.offer(cur.rt);
				}
			}
			L++;
		}
		return L;
	}

	public static void main(String[] args) {
		Main tree = new Main();
		tree.root = new Node(1);
		tree.root.lt = new Node(2);
		tree.root.rt = new Node(3);
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		Scanner kb = new Scanner(System.in);
		System.out.print(tree.BFS(tree.root));
	}
}

 

12. 경로탐색(DFS)

import java.util.*;

class Main {
	static int n, m, answer = 0;
	static int[][] arr;
	static int[] ch;

	public void DFS(int cur) {
		if (cur == n) {
			answer++;
		} else {
			for (int i = 1; i < n + 1; i++) {
				if (arr[cur][i] == 1 && ch[i] == 0) {
					ch[i] = 1;
					DFS(i);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		arr = new int[n + 1][n + 1];
		ch = new int[n + 1];
		for (int i = 0; i < m; i++)
			arr[kb.nextInt()][kb.nextInt()] = 1;
		ch[1] = 1;
		T.DFS(1);
		System.out.print(answer);
	}
}

 

13. 경로탐색(인접리스트, ArrayList)

import java.util.*;

class Main {
	static int n, m, answer = 0;
	static ArrayList<ArrayList<Integer>> graph;
	static int ch[];

	public void DFS(int v) {
		if (v == n)
			answer++;
		else {
			for (int i = 0; i < graph.get(v).size(); i++) {
				int nv = graph.get(v).get(i);
				if (ch[nv] == 0) {
					ch[nv] = 1;
					DFS(nv);
					ch[nv] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		graph = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < n; i++)
			graph.add(new ArrayList<Integer>());
		ch = new int[n + 1];
		for (int i = 0; i < m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			graph.get(a).add(b);
		}
		ch[1] = 1;
		T.DFS(1);
		System.out.println(answer);
	}
}

 

14. 그래프 최단거리(BFS)

import java.util.*;

class Main {
	static int n, m, L = 1;
	static ArrayList<ArrayList<Integer>> graph;
	static int ch[];
	static int dis[];

	public void BFS(int v) {
		Queue<Integer> Q = new LinkedList<>();
		Q.offer(v);
		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				int cv = Q.poll();
				for (int j = 0; j < graph.get(cv).size(); j++) {
					int nv = graph.get(cv).get(j);
					if (ch[nv] != 1) {
						ch[nv] = 1;
						dis[nv] = dis[cv] + 1;
						Q.offer(nv);
					}
				}
			}
			L++;
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		graph = new ArrayList<ArrayList<Integer>>();
		dis = new int[n + 1];
		for (int i = 0; i < n + 1; i++)
			graph.add(new ArrayList<Integer>());
		ch = new int[n + 1];
		for (int i = 0; i < m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			graph.get(a).add(b);
		}
		ch[1] = 1;
		T.BFS(1);
		for (int x : dis)
			System.out.print(x + " ");
	}
}

 

 

 

'알고리즘 > JAVA' 카테고리의 다른 글

Greedy Algorithm  (0) 2021.10.04
DFS, BFS 활용  (0) 2021.09.27
10. 마구간 정하기(결정알고리즘)  (0) 2021.09.25
9. 뮤직비디오(결정알고리즘)  (0) 2021.09.25
8. 이분검색  (0) 2021.09.25

관련글

댓글

티스토리툴바