BFS / DFS (java)

 

출처: 나무위키

 

 

1. BFS (너비 우선 탐색)

끝까지 탐색하는게 아닌 층별로 탐색하면서 해답을 찾으면 종료

최단거리 구하는 문제에서 사용 (Queue)

 

문제:https://www.acmicpc.net/problem/2178

	Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0,0));  //시작노드 삽입

        visited[0][0] = 0;
        while(!queue.isEmpty()){
            Node node = queue.poll();

            node.step++;
            if(node.x == (N-1) && node.y == (M-1)){  //종료조건 (해답을찾으면종료)
                output.write(node.step+"\n");
                break;
            }
			
            //다음 층의 탐색할 노드들 (상하좌우)
            if(node.x>0 && visited[node.x-1][node.y]==1){
                visited[node.x-1][node.y] = 0;
                queue.offer(new Node(node.x-1,node.y,node.step));
            }if(node.y>0 && visited[node.x][node.y-1]==1){
                visited[node.x][node.y-1] = 0;
                queue.offer(new Node(node.x,node.y-1,node.step));
            }if(node.x<(N-1) && visited[node.x+1][node.y]==1){
                visited[node.x+1][node.y] = 0;
                queue.offer(new Node(node.x+1,node.y,node.step));
            }if(node.y<(M-1) && visited[node.x][node.y+1]==1){
                visited[node.x][node.y+1] = 0;
                queue.offer(new Node(node.x,node.y+1,node.step));
            }
        }

 

위 예제는 한번 방문한 자리는 다른 탐색 시 에서도 방문할 필요가 없어 visited를 공유했지만

각각 따로 저장해야 할 경우도 있다.

 

 

2. DFS (깊이 우선 탐색)

층별이 아닌 각 노드의 끝까지 탐색한다.

모든 경우의 수를 탐색해야 할 때 사용

 

문제:https://www.acmicpc.net/problem/1012

 

public static void dfs(int x, int y, int C){
	if(x<0 || x>=M) return;
	if(y<0 || y>=N) return;

	if(arr[x][y]==1 && !visited[x][y]){    //방문한곳은 재방문하지 않음
		visited[x][y] = true;     //방문표시

		dfs(x+1,y,C);
		dfs(x-1,y,C);
		dfs(x,y+1,C);
		dfs(x,y-1,C);
	}
}