Recursive, Tree, Graph(DFS, BFS 기초)
유형
1.재귀함수(스택 프레임)
//문제
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
//입력
3
//출력
1 2 31.그냥 for문을 이용한 풀이 -> 생략
2.재귀 : 스택 프레임을 이용한 풀이
public class ex1_2 {
public static void solution(int n){
if(n==0) return;
else{
solution(n-1);
System.out.print(n + " ");
//재귀함수는 스택프레임을 사용한다.
//호출이 끝나면 전 함수로 복귀한다.
//빽 트래킹
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
solution(n);
}
}풀이
1.재귀 함수를 만들어서 계속 호출한다.
2.이때 함수는 스택구조를 가진다.
2.이진수 출력(재귀)
//문제
10진수->2진수
//입력
11
//출력
1011public class ex2 {
public static void DFS(int n){
if(n==0) return;
else{
DFS(n/2);
System.out.print(n%2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
DFS(n);
}
}풀이
재귀를 이용한다. 2의 몫을 호출하고 호출이 끝나면 순차적으로 2로 나눈 나머지를 출력한다.
3.팩토리얼
//문제
재귀를 이용한 팩토리얼
//입력
5
//출력
120public class ex3 {
public static int factorial(int n){
if(n<=1) return n;
else return n * factorial(n-1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(factorial(n));
}
}풀이
재귀 사용
4.피보나치 수열
//문제
//입력
//출력1.기본 재귀 풀이
public class ex4 {
public static int fibonacci(int n){
if(n==1||n==2) return 1;
else {
int a = fibonacci(n-1) + fibonacci(n-2);
return a;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=1; i<=n; i++){
System.out.print(fibonacci(i) + " ");
}
}
}풀이
기본적인 재귀를 이용한 피보나치 수열을 구하는 방식이다.
2.메모이제이션 + 스택 프레임 (중요)
public class ex4_2 {
static int[] fibo;
public static int fibonacci(int n){
//핵심 //fibo(배열)의 값은 0으로 초기화 되어있는 것을 이용
//해당 n값이 구해져있으면 그거 가져다 쓴다는 뜻.
if(fibo[n]>0) return fibo[n];
if(n==1||n==2) return fibo[n]=1;
else return fibo[n] = fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
fibo=new int[n+1];
fibonacci(n);
for(int i=1; i<=n; i++){
System.out.print(fibo[i]+" ");
}
}
}풀이
1.배열을 새로하나 만들어서 배열에 값을 기록해 그 배열의 값을 출력하는 방식 -> 시간이 좀 더 빨라짐
2.모든 배열은 선언되면 0으로 초기화되기 때문에 if(fibo[n]>0) return fibo[n]; 을 이용해서 이미 구해져있는 부분은 끌어다 사용 -> 완전 빨라짐
5.이진트리 순회(깊이우선탐색)
//문제
아래 그림과 같은 이진트리를 전위,중위,후위 순회를 연습해보세요.
//출력
전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1class Node{
int data;
Node lt,rt; //node객체의 주소를 저장하는 변수
public Node(int val){
data=val;
lt=rt=null;
}
}
public class ex5 {
Node root;
public void DFS(Node root){
if(root==null) return;
else{
System.out.println(root.data + " "); -> 전위
DFS(root.lt);
System.out.println(root.data + " "); -> 중위
DFS(root.rt);
System.out.println(root.data + " "); -> 후위
}
}
public static void main(String[] args) {
ex5 tree = new ex5();
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.Node클래스를 만든다.
3.Node클래스에 그림과 같이 값을 삽입한다.
4.DFS()를 계속 호출해서 root가 없으면 빽트래킹을 시키고 아니라면 계속 재귀함수를 호출한다.
[ 주요기능 ]
스택 프레임의 구조를 잘 생각해서 출력하면 된다.
6.부분집합 구하기(DFS)
//문제
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력
//입력
3
//출력
1 2 3
1 2
1 3
1
2 3
2
3class ex6 {
static int n;
static int[] ch;
public void DFS(int L){
if(L==n+1){
String tmp="";
for(int i=1; i<=n; i++){
if(ch[i]==1) tmp+=(i+" ");
}
if(tmp.length()>0) System.out.println(tmp);
}
else{
ch[L]=1;
DFS(L+1);
ch[L]=0;
DFS(L+1);
}
}
public static void main(String[] args){
ex6 T = new ex6();
n=3;
ch=new int[n+1];
T.DFS(1);
}
}풀이
1.DFS()와 값을 저장할 ch[]배열을 만든다.
2.DFS()를 호출시켜서 입력되는 숫자 n의 크기를 넘을 때 빽트래킹을 하면서 체킹 해뒀던 ch[]의 값을 출력한다.
7.이진트리 순회(넓이우선탐색 : 레벨탐색)
//문제
아래 그림과 같은 이진트리를 레벨탐색 연습하세요.
//출력
0 : 1
1 : 2 3
2 : 4 5 6 7 class Node2 {
int data;
Node2 lt,rt; //node객체의 주소를 저장하는 변수
public Node2(int val){
data=val;
lt=rt=null;
}
}
public class ex7 {
Node2 root;
public void BFS(Node2 root) {
Queue<Node2> 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++){
Node2 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) {
ex7 tree = new ex7();
tree.root = new Node2(1);
tree.root.lt = new Node2(2);
tree.root.rt = new Node2(3);
tree.root.lt.lt = new Node2(4);
tree.root.lt.rt = new Node2(5);
tree.root.rt.lt = new Node2(6);
tree.root.rt.rt = new Node2(7);
tree.BFS(tree.root);
}
}풀이
1.순회 문제와 같은 구조로 Node 클래스를 만들고 값을 삽입해서 만든다.
2.BFS()를 만들어 호출될 때마다 Q에 있는 값을 Q.poll()을 해주면서 그 Q.poll()되어서 나오는 값들의 lt,rt가 있으면 그것들을 Q.offer()해준다.
[ 주요 기능 ]
1.BFS는 기본적으로 Queue의 구조를 가진다.
8.송아지 찾기(BFS : 상태트리탐색)
//문제
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할
수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하라
//입력
5 14
//출력
3public class ex8 {
public static int BFS(int s,int e){
int[] dis={1,-1,5};
int[] ch = new int[10001];
Queue<Integer> Q = new LinkedList<>();
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){
ch[nx]= 1;
Q.offer(nx);
}
}
}
L++;
}
return L;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int e = sc.nextInt();
System.out.println(BFS(s,e));
}
}풀이
1.몇 번의 점프로 -> 최단거리 -> BFS
2.점프를 담은 배열 dis[], 중복 방지를 위해 값을 체크 할 ch[],길이를 리턴 할 L을 선언한다.
3.BFS원리인 Queue방식대로 돌리고 Q.poll할때 마다 자식노드를 넣는다. 이때 자식노드는 Q.poll()+dis[j]가 된다.
9.Tree 말단 노드까지의 가장 짧은 경로(DFS)
//문제
말단 노드까지의 가장 짧은 경로를 구하라. DFS 방식사용.class Node3 {
int data;
Node3 lt,rt; //node객체의 주소를 저장하는 변수
public Node3(int val){
data=val;
lt=rt=null;
}
}
class ex9 {
static Node3 root;
public static int DFS(int L, Node3 root){
if(root.lt==null && root.rt==null) return L;
else return Math.min(DFS(L+1,root.lt),DFS(L+1,root.rt));
}
public static void main(String[] args) {
root=new Node3(1);
root.lt=new Node3(2);
root.rt=new Node3(3);
root.lt.lt=new Node3(4);
root.lt.rt=new Node3(5);
System.out.println(DFS(0,root));
}
}풀이
1.Node클래스를 만든다. 그림 처럼 값을 삽입한다. 호출.
2.재귀가 돌면서 DFS방식으로 탐색한다.자식노드인 lt,rt로 한칸씩 갈 수록 L도 +1씩 증가한다. 자식노드가 둘 다 없으면서 더 작은 L값을 가지는
노드의 L값을 리턴한다.
10.Tree 말단 노드까지의 가장 짧은 경로(BFS)
//문제
말단 노드까지의 가장 짧은 경로를 구하라. DFS 방식사용.class Node4 {
int data;
Node4 lt,rt; //node객체의 주소를 저장하는 변수
public Node4(int val){
data=val;
lt=rt=null;
}
}
public class ex10 {
static Node4 root;
public static int BFS(Node4 root) {
Queue<Node4> Q = new LinkedList<>();
Q.offer(root);
int L=0;
while(!Q.isEmpty()){
int len=Q.size();
for(int i=0; i<len; i++){
Node4 poll= Q.poll();
if(poll.lt ==null && poll.rt ==null) return L;
if(poll.lt!=null) Q.offer(poll.lt);
if(poll.rt!=null) Q.offer(poll.rt);
}
L++;
}
return L;
}
public static void main(String[] args) {
root = new Node4(1);
root.lt = new Node4(2);
root.rt = new Node4(3);
root.lt.lt = new Node4(4);
root.lt.rt = new Node4(5);
System.out.print(BFS(root));
}
}풀이
1.Q.poll()하면서 그 논드의 자식이 있으면 Q.offer()로 담는게 원래 방식.
2.자식이 둘다 없으면 현재 L(레벨)값을 리턴.
11.그래프와 인접
G(V,E)가 주어지면 이 E(간선)의 방향을 체크하는 graph[][]에서 무방향(양방향)을 체킹할 수 있다.
1.무방향(양방향) 그래프
graph[a][b]=1;
graph[b][a]=1;2.방향 그래프
graph[a][b]=1;3.가중치 방향 그래프
graph[a][b]=c;12.경로 탐색(인접행렬)
//문제
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램 작성
//입력
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
//출력
6public class ex12 {
static int n=0,m=0,answer=0;
static int[][] graph;
static int[] ch;
public static void DFS(int v){
if(v==n) answer++;
else{
for(int i=1; i<=n; i++){
if(graph[v][i] == 1 && ch[i]==0){
ch[i]=1;
DFS(i);
ch[i]=0;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
graph=new int[n+1][n+1];
ch=new int[n+1];
for(int i=0; i<m; i++){
int a= sc.nextInt();
int b= sc.nextInt();
graph[a][b]=1;
}
ch[1]=1;
DFS(1);
System.out.println(answer);
}
}풀이
1.정답을 체킹할 answer, 입력받는 정점의수 n, 간선의수 e를 전역으로 static선언 그리고 방향을 체크할 graph[][]를 선언. 마지막으로 방문했던 노드를 체크하기 위한 ch[]을 선언한다.
2.graph[][],ch[]를 선언하고 입력받는 m만큼 a,b를 입력받아 graph[a][b]=1을 체크한다.
3.노드1번은 항상 시작하기 때문에 ch[1]=1로 해둔다.
4.DFS()함수에서 if문을 v==n으로 해서 n에 도달하면 answer++를 한다.
5.else문에서 for문으로 1~n만큼 다 돌려서 graph[v][i]가 1이면서 ch[i]==0인 곳을 방문하게 만들고, ch[]를 1로 체크하고 DFS(i)로 더 깊이 들어간다. 다시 나오게 되면 ch[i]=0; 으로 만들어 준다.
13.경로 탐색(인접리스트)
//12번과 같은 문제public class ex13 {
static int n=0,m=0,answer=0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch;
public static void DFS(int v){
if(v==n) answer++;
else{
for(int nv : graph.get(v)){
if(ch[nv]==0){
ch[nv]=1;
DFS(nv);
ch[nv]=0;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.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= sc.nextInt();
int b= sc.nextInt();
graph.get(a).add(b);
}
ch[1]=1;
DFS(1);
System.out.println(answer);
}
}
풀이
1.전체적인 풀이는 위와 비슷하다. 인접리스트를 이용해서 경로를 탐색하는 방식은 정점이 1000이상 , 10000이상 많을 때 사용한다.
2.graph[a][b]==1 인지 볼필요가 없다.입력받는 노드에대한 각 간선을 graph.get(a).add(b)를 해주면 된다.
3.DFS()함수에서 forEach문으로 돌면서 각각의 노드를 graph.get(v)해서 가져온다음에 해당하는 방향으로 n에 도달하면 answer++;
14.💥 그래프 최단거리(BFS)(어려움)
//문제
1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.
//입력
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5
//출력
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2public class ex14 {
static int n, m, answer=0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;
public static void BFS(int v){
ch[v]=1;
dis[v]=0;
Queue<Integer> Q=new LinkedList<>();
Q.offer(v);
while(!Q.isEmpty()){
int x=Q.poll();
for(int nx : graph.get(x)){
if(ch[nx]==0){
ch[nx]=1;
Q.offer(nx);
dis[nx]=dis[x]+1;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
graph=new ArrayList<ArrayList<Integer>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Integer>());
}
ch=new int[n+1];
dis=new int[n+1];
for(int i=0; i<m; i++){
int a=sc.nextInt();
int b=sc.nextInt();
graph.get(a).add(b);
}
BFS(1);
for(int i=2; i<=n; i++){
System.out.println(i+" : "+dis[i]);
}
}
}풀이
1. 인접배열이아닌 인접리스트로 풀어야 한다. 입력값 크기에 따른 런타임에러 방지.
2. graph=new ArrayList<ArrayList>(); 로 인접리스트 그래프를 만든다.
3. 방문했던 정점인지 아닌지 체크용 ch[], 거리를 담을 dis[]선언
4. 간선 방향을 그림처럼 입력 후 , 그래프에 해당 정점에 간선을 추가.
5. BFS 1번 정점부터 시작
