4 min to read

DFS와 BFS

DFS와 BFS를 배워봅시다.

Imagem de capa

백준 알고리즘 1260번

DFS (Depth First Search) 깊이 우선 탐색

인접해 있는 점 순으로 탐색해 나감 ( 재귀 사용 )

public static void dfs(int i){
    visited[i] = true;
    System.out.print(i+" ");

    for(int j=1; j<=N; j++){
        if(graph[i][j]==1&& visited[j]==false){
            dfs(j);
        }
    }
}

BFS (Breadth First Search) 너비 우선 탐색

가까운 정점 먼저 탐색 후 점차 한단계씩 탐색해 나감 ( 큐 )

public static void bfs(int i){
    Queue<Integer> q = new LinkedList<Integer>();
    q.offer(i);
    visited[i] = true;
    System.out.print(i+" ");

    int temp;
    while(!q.isEmpty()){
        temp = q.poll();
        for(int j=0; j<N+1; j++){
            if(graph[temp][j]==1&&visited[j]==false){
                q.offer(j);
                visited[j]=true;
                System.out.print(j+" ");
            }
        }
    }
}

미로찾기 ( BFS 사용 )

백준 알고리즘 2178번

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    Queue<Integer> q=new LinkedList<Integer>();
    int N=sc.nextInt();
    int M=sc.nextInt();
    boolean[][] visit=new boolean[N][M];
    int[][] map=new int[N][M];
    int[] trace=new int[N*M];

    //한 방향씩 이동하기 위한 준비입니다.
    int[] way_x={-1,0,1,0};
    int[] way_y={0,1,0,-1};

    for(int i=0;i<N;i++){
        String temp=sc.next();
        for(int j=0;j<M;j++){
            map[i][j]=temp.charAt(j)-'0';
        }
    }
	//x를 0, y를 0으로 시작점을 잡습니다.
    q.offer(0);
    q.offer(0);
    visit[0][0]=true;

	//큐가 비어있지 않으면 큐에서 x, y를 빼내고 목적지에 도달했으면 종료.
    //그렇지 않으면 상하좌우로 한번씩 이동해 보면서 이동할 수 있으면 큐에 집어넣습니다.
    while(!q.isEmpty()){
        int x=q.poll();
        int y=q.poll();
        if(x==N-1&&y==M-1){
            break;
        }

        for(int i=0;i<4;i++){
            int tx=x+way_x[i];
            int ty=y+way_y[i];
            if(tx>=0&&tx<N&&ty>=0&&ty<M){
                if(map[tx][ty]==1&&visit[tx][ty]==false){
                    q.offer(tx);
                    q.offer(ty);
                    visit[tx][ty]=true;
                    trace[M*tx+ty]=M*x+y;
                }
            }
        }
    }
    int t=N*M-1;
    int num=1;
    while(t!=0){
        t=trace[t];
        num++;
    }
    System.out.println(num);
}