DFS, BFS 활용 섹션 - (3)

DFS, BFS 활용 섹션 -(3)

8-8. 수열 추측하기

import java.util.Scanner;

/*8-8. 수열 추측하기  | DFS *** 조금 어렵다.
*/
public class Main1 {
    static int[] b, p, ch;
    static int n, f;
    boolean flag = false;
    int[][] dy = new int[35][35];

    //combi 조합
    public int combi(int n, int r) {
        if(dy[n][r]>0) return dy[n][r];
        if(n==r || r==0) return 1;
        else return dy[n][r] = combi(n-1, r-1)+ combi(n-1, r);
    }

    //dfs 함수 
    public void DFS(int L, int sum) {
        if(flag) return; //그러면 리턴
        if(L==n) { //n개 중에서 n개 뽑은 순열 완성됨
            if(sum == f) {
                for(int x: p) System.out.print(x + " ");
                flag = true;
            }
        }else {
            for(int i=1; i<=n; i++) {
                if(ch[i] == 0) {
                    ch[i] = 1;
                    p[L] = i;
                    DFS(L+1, sum+(p[L]*b[L]));
                    //복귀하면서 탐색해야 함
                    ch[i]=0;
                }
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        f = kb.nextInt();

        //조합 확인용 배열 
        b = new int[n];
        //정답 확인용 배열 (순열) 
        p = new int[n];
        //방문 체크용 배열
        ch = new int[n+1];

        //입력이 n으로 들어오면 b[] 내부를 n-1의 조합들로 초기화
        for(int i=0; i<n; i++) {
            b[i] = T.combi(n-1, i);
        }

        //호출
        T.DFS(0, 0);        
    }
}

---

8-9. 조합 구하기 | DFS | 외워버리기

import java.util.Scanner;

/* 8-9. 조합 구하기 | DFS | 외워버리기 */
public class Main2 {
    static int[] combi;
    static int n, m;
    //DFS
    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[L]=i;
                DFS(L+1, s+1);
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        combi = new int[m];
        T.DFS(0, 1); //0레벨 1부터 시작
    }
}

---

8-10. 미로탐색 (DFS)

import java.util.Scanner;

/* 8-10. 미로탐색 (DFS) */
public class Main3 {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board;
    static int answer = 0;
    //DFS
    public void DFS(int x, int y) {
        if(x == 7 && y ==7) {
            answer++;
        }
        else {
            //4방향으로 돌면서
            for(int i=0; i<4; i++) {
                int nx = x + dx[i];//다음 x 방향 
                int ny = y + dy[i];//다음 y 방향 
                //보드 경계 벗어나지 않도록 제한 걸어두기  (범위 내이면서 + 방문 전 0 인 대상만)
                if(nx>=1 && nx<=7 && ny >=1 && ny <=7 && board[nx][ny] == 0) {
                    board[nx][ny] = 1; //방문 체크
                    DFS(nx, ny);
                    //다시 복귀
                    board[nx][ny] = 0;
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        board = new int[8][8];
        for(int i=1; i<=7; i++) {
            for(int j =1; j<=7; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //출발점 세팅 
        board[1][1]=1;
        T.DFS(1, 1);
        System.out.println(answer);
    }
}

---

8-11. 미로의 최단 거리 통로 (BFS)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 8-11. 미로의 최단 거리 통로 (BFS) */
class Point{
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main4 {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, dis;
    //BFS
    public void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        //들어온 좌표 넣고
        Q.offer(new Point(x, y));
        board[x][y] = 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 >=1 && nx <=7 && ny>=1 && 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;//이전 값 +1씩 길이 측정
                }
            }
        }
    }
    //실행 메인
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb= new Scanner(System.in);

        board = new int[8][8];
        dis = new int[8][8];

        for(int i=1; i<=7; i++) {
            for(int j =1; j<=7; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //호출
        T.BFS(1, 1);
        if(dis[7][7] == 0) System.out.println(-1);
        else System.out.println(dis[7][7]);
    }
}

---