백준 알고리즘 1260번 DFS와 BFS

1. 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

장점과 단점[편집]

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

2. 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

장점과 단점[편집]

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/1260

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

public class Test1260{
	static int N,M,V;
	static int visit[], graph[][];

  static void DFS(int x) {
		visit[x]=1;
		System.out.print(x+" ");
		for(int i=1; i<=N; i++) {
			if(graph[x][i]==1 && visit[i]==0) {
				DFS(i);
			}
		}
	}
	static void BFS() {
		Queue<Integer> q = new LinkedList<Integer>();
		visit[V] = 1;
		q.add(V);
		while(!q.isEmpty()) {
			int x = q.peek(); //Queue에서 제거하며 읽기
			q.poll(); //Queue에서 제거하지 않고 읽기
			System.out.print(x+" ");
			for(int i=1; i<=N; i++) {
				if(graph[x][i]==1 && visit[i]==0) {
					visit[i]=1;
					q.add(i);
				}
			}
		}
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		V = sc.nextInt();
		
		graph = new int[N+1][N+1];
		for(int i=1; i<=M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			graph[x][y]=graph[y][x]=1;
		}

		visit = new int[N+1];
		DFS(V);
		System.out.println();
		visit = new int[N+1];
		BFS();
		
	}
	
}
　

결과는 다음과 같습니다.