import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public 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();
T.DFS(3);
}
}
- python
2) 재귀함수를 이용한 이진수 출력
- java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public 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();
T.DFS(11);
}
}
- python
++ 이진트리 깊이 탐색
전위: 부모 - 왼 - 오
중위: 왼 - 부모 - 오
후위: 왼 - 오 - 부모
>> 부모의 위치가 전 , 중 , 후
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public void DFS(int v){
if(v > 7) return;
else {
System.out.print(v + " ");
DFS(v*2);
DFS(v*2+1);
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(1);
}
}
3) 중복순열
- java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
Stack<Integer> stack = new Stack<>();
static int n=3, m=2;
public void DFS(int l){
if(l == m){
for(int x : stack) System.out.print(x + " ");
System.out.println();
} else {
for(int i=1; i<=n; i++){
stack.push(i);
DFS(l+1);
stack.pop();
}
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(0);
}
}
- python
4) 순열 구하기
- java
package ch06;
import java.io.*;
import java.util.*;
public class 순열구하기 {
static int[] ch, arr;
static int n, m;
Stack<Integer> pm = new Stack<>();
public void DFS(int L){
if(L==m){
for(int x : pm) System.out.print(x+" ");
System.out.println();
}
else{
for(int i=0; i<n; i++){
if(ch[i]==0){
ch[i]=1;
pm.push(arr[i]);
DFS(L+1);
ch[i]=0;
pm.pop();
}
}
}
}
public static void main(String[] args){
순열구하기 T = new 순열구하기();
Scanner kb = new Scanner(System.in);
n=kb.nextInt();
m=kb.nextInt();
arr=new int[n];
for(int i=0; i<n; i++) arr[i]=kb.nextInt();
ch=new int[n];
T.DFS(0);
}
}
- python
5) 가장 가까운 큰수
- java
package ch06;
import java.io.*;
import java.util.*;
public class 가장가까운큰수 {
int answer=0, target, m;
ArrayList<Integer> nums=new ArrayList<>();
Stack<Integer> pm = new Stack<>();
int[] ch;
boolean flag=false;
public void DFS(int L){
if(flag) return;
if(L==m){
answer=0;
for(int x : pm) answer=answer*10+x;
if(answer>target) flag=true;
}
else{
for(int i=0; i<m; i++){
if(ch[i]==0){
ch[i]=1;
pm.push(nums.get(i));
DFS(L+1);
ch[i]=0;
pm.pop();
}
}
}
}
public int solution(int n){
target=n;
int tmp=n;
while(tmp>0){
int t=tmp%10;
nums.add(t);
tmp=tmp/10;
}
Collections.sort(nums);
m=nums.size();
ch=new int[m];
DFS(0);
if(flag==false) return -1;
return answer;
}
public static void main(String[] args){
가장가까운큰수 T = new 가장가까운큰수();
System.out.println(T.solution(123));
}
}
- python
6) 조합 구하기
- java
import java.util.*;
class Main{
static int n, m;
Stack<Integer> combi = new Stack<>();
public void DFS(int L, int s){
if(L==m){
for(int x : combi) System.out.print(x+" ");
System.out.println();
}
else{
for(int i=s; i<=n; i++){
combi.push(i);
DFS(L+1, i+1);
combi.pop();
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt();
m=kb.nextInt();
T.DFS(0, 1);
}
}
- python
++ 이진트리 레벨 탐색
[1, 2, 3, 4, 5, 6, 7]
import java.util.*;
class Main {
ArrayList<Integer> answer = new ArrayList<>();
public ArrayList<Integer> solution(int n){
Queue<Integer> Q=new LinkedList<>();
Q.offer(1);
int L=0;
while(!Q.isEmpty()){
int len=Q.size();
for(int i=0; i<len; i++){
int v=Q.poll();
answer.add(v);
for(int nv : new int[]{v*2, v*2+1}){
if(nv>n) continue;
Q.offer(nv);
}
}
L++;
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(7));
}
}
7) 송아지 찾기
- java
import java.util.*;
class Main {
public int solution(int s, int e){
int ans;
Queue<Integer> q = new LinkedList<>();
int[] check = new int[10001];
q.offer(s);
check[s] = 1;
int l = 0;
while(!q.isEmpty()){
int len = q.size();
for(int i=0; i<len; i++){
int x = q.poll();
for(int nx : new int[]{x+1, x-1, x+5}){
if(nx == e) return l+1;
if(nx >= 1 && nx <= 10000 && check[nx] == 0){
check[nx] = 1;
q.offer(nx);
}
}
}
l++;
}
return 0;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(8, 3));
}
}
- python
8) 미로의 최단거리 통로
- java
import java.util.*;
class Point {
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
class Main {
public int solution(int[][] board){
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int[][] dis = new int[7][7];
Queue<Point> q = new LinkedList<>();
q.offer(new Point(0, 0));
board[0][0] = 1;
while(!q.isEmpty()){
Point tmp = q.poll();
for(int i=0; i<4; i++){
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if(nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && board[nx][ny] == 0){
board[nx][ny] = 1;
q.offer(new Point(nx, ny));
dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
}
}
}
if(dis[6][6] == 0) return -1;
else return dis[6][6];
}
public static void main(String[] args){
Main T = new Main();
int[][] arr = new int[][]{{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 1},
{1, 1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0, 0}};
System.out.println(T.solution(arr));
}
}
