DFS v BFS

**DFS : 모든 경우를 만들어 보는 코드, n명 중에서 순서에 상관없이 m명을 뽑는 경우의 수

**BFS : 어떤 대상을 조건에 맞게 동작하도록 코드가 쉽게 구현됨, 상어가 움직이는데 이렇게 동작하고 결과는 어떻게??

 

 

DFS

 

 

**DfsExam1

package Algorithm;

 

import java.util.Scanner;

 

public class DfsExam1 {

static int T;//반복할 수

    static int N;//조합하고 싶은 수(Maximum<=6)단계 깊이

    static int visited[] = new int[7];//지나간 경로

    static int Answer[] = new int[7];

   

    static void dfs(int depth) {

            if(depth==N+1) {

            for(int i=1;i<=N;i++) {

            System.out.print(Answer[i]+" ");

            }

            System.out.println();

            }else {

            for(int i=1;i<=N;i++) {

            if(visited[i]==0) {//방문하지 않은 곳이라면

            visited[i]=1;//일단 이 곳은 내가 간 곳이기 때문에

            Answer[depth] = i;

            dfs(depth+1);

            visited[i]=0;

            Answer[depth]=0;

            }

            }

          }

    }

   

    public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);

            T = sc.nextInt();

            for(int test_case=1;test_case<=T;test_case++) {

            N = sc.nextInt();

            for(int i=1; i<=N;i++) {

            visited[i]= 0;//값 초기화

            }

            dfs(1);//1부터 시작해서 점점 키워나갈 것

            System.out.println("#" + test_case);

            }

    }

}

 

**DfsExam2

package Algorithm;

 

import java.util.Scanner;

 

public class DfsExam2 {

static int T;//반복할 수

    static int N,M; //게임을 2,3번 할것이기 때문에 static선언 ,도시 수 & 출발도시

    static int Answer;

    static int MAT[][] = new int[11][11];

    static int visited[] = new int[11];//게임할때마다 리셋해줘야 함.

   

   

    public static void dfs(int idx, int cnt, int cost) {//현재위치,방문도시의 수, 비용

    //종료조건 = 모든 도시를 방문했을 때, 시작점으로 돌아갈 길이 있는 경우

    if(cnt == N && MAT[idx][M]!=0) { //다 돌았으면(도시수가 N이거나 현재 위치에서 출발도시로 가는 길이 있으면)

    //기존 답보다 새로운 비용이 더 적은 경우를 찾기

    if(Answer == 0 || Answer > cost +MAT[idx][M]) { //answer값이 없거나 구하려는 값이 cost돌린값보다 클때

    Answer = cost + MAT[idx][M]; //cost가 더 작기때문에

    }

   

    }else {//탐색조건 = 방문한 적이 없고, 길이 있는 도시만 검색

    for(int i=1;i<=N;i++) {

    if(visited[i]==0 && MAT[idx][i] !=0) {//내가 갔던 길이 아니고, 현재위치에서 i로 가는 길이 있어야 함

    //가지치기를 잘해야함.(기존 정답보다 누적비용이 작은 경우 => 탐색 필요)

    if(Answer ==0 || Answer > cost + MAT[idx][i]) {//answer가 더 크다. 재귀함수로 더 돌려야 하는 가치가 있다.

    visited[i]=1;//한번 방문한 값으로 바꾸고

    dfs(i,cnt+1,cost+MAT[idx][i]);

    visited[i]=0; //값 리셋

    }

    }

    }

    }

    }

 

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

        T = sc.nextInt();

        for(int test_case=1;test_case<=T;test_case++) {

                N = sc.nextInt();//도시 수

                M = sc.nextInt();//출발 도시

               

                for(int i=1;i<=N;i++) {

                for(int j=1;j<=N;j++) {//비용초기화

                MAT[i][j] =0;

                }

                }

                for(int i=1;i<=N;i++) {//값 초기화

                visited[i]=0;

                }

                for(int i=1;i<=N;i++) {

                for(int j=1;j<=N;j++) {

                MAT[i][j] = sc.nextInt();//값 입력받음

                }

                }

                visited[M] = 1;

                Answer = 0;

                //DFS 탐색(위치, 현재까지 방문한 도시의 수, 비용)

                dfs(M,1,0);

                System.out.println("#"+test_case + " "+Answer);

        }

}

 

}

 

**DfsExam3

 

package Kosta.Algorithm;

 

import java.util.ArrayList;

import java.util.Scanner;

 

public class DfsExam3 {

static int T, N;

static ArrayList<int[]> S = new ArrayList<int[]>();//화산위치 저장

//-1:파괴된 초원, 0:초원, 1:바리케이트, 2:화산

static int MAT[][] = new int[101][101];//지도값 저장

//상하좌우 탐색

static int dr[] = {0, 0, -1, 1}; //0, 1, 2, 3

static int dc[] = {1, -1, 0, 0}; //0, 1, 2, 3 //동서남북

static int Answer;

public static void dfs(int now_row, int now_col) {

//탐색조건 , 종료조건이 불필요

for(int i=0;i<4;i++) {

int nxt_row = now_row + dr[i];

int nxt_col = now_col + dc[i];

//다음 지점이 격자 안에 있는 경우

if(nxt_row >=1 && nxt_row <= N && nxt_col >=1 && nxt_col <= N) {

if(MAT[nxt_row][nxt_col] == 0) {  //초원을 만나면

MAT[nxt_row][nxt_col]  = -1;  //초원을 파괴한다.

Answer--;  //남는 초원수를 감소시킨다.

dfs(nxt_row, nxt_col);  //용암이 퍼져 흐르는 것을 재귀함수로 호출

}

}

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

T = sc.nextInt(); //test case 수

for(int test_case=1;test_case<=T;test_case++) {

N = sc.nextInt(); //test cast 수대로 몇행 몇열 만들것인지 입력

//지도 초기화

for(int i=1;i<=N;i++) {

for(int j=1;j<=N;j++) {

MAT[i][j] = 0;//map초기화

}

}

S.clear(); //ArrayList를 완전히 비운다.

Answer = 0; //Answer값 초기화

//지도 입력 받기

for(int i=1;i<=N;i++) {

for(int j=1;j<=N;j++) {

MAT[i][j] = sc.nextInt();

if(MAT[i][j] == 0) {

Answer++; //초원일 경우 answer답 +

}else if(MAT[i][j] == 2) { //2를 만났을때

S.add(new int[] {i, j});//화산이 일어나는 지점의 좌표를 arraylist에 저장

}//end else

}//inner for

}//outer for

for(int i=0;i<S.size();i++) { //arraylist의 get메소드는 값을 가져오는 것. ->

dfs(S.get(i)[0], S.get(i)[1]); //int now_row, int now_col

}

System.out.println("#" + test_case + "  " + Answer);

}

}

}