[백준 1260][자바] DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

🔑가장 기본인 BFS,  DFS  구현 문제!

 

 

BFS DFS 설명 게시글 참고! (나중에 URL 추가 예정)

 

📌 BFS (Breath-First-Search, 너비 우선 탐색)

- 큐로 구현!

- while(!que.isEmpty)

- 한 포인트에서 갈 수 있는 포인트들 다 넣고 탐색이 끝나면

- 그다음 포인트(큐에서 poll(); 시키고 )에서 갈 수 있는 포인트들 탐색.

 

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

- 재귀나 스택으로 구현! (재귀선택)

- 한점에서 연결된 포인트들 재귀함수를 써서 계속 끝까지 탐색.

 

---

import java.util.*;

public class bdfs {
	public static int[][] arr;
	public static boolean[] visited;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        
		int point = scan.nextInt();
		int line = scan.nextInt();
		int start = scan.nextInt();
		
		arr = new int[point+1][point+1];
		
		for(int i=1;i<=line;i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
//		for(int i=1; i<arr.length;i++) { //행렬보기
//			for(int j=1;j<arr.length;j++) {
//				System.out.print(arr[i][j]);
//			}
//			System.out.println();
//		}
		
        // 깊이우선탐색
		visited = new boolean[point+1];
		dfs(start); 
		
		System.out.println();
        
        // 너비우선탐색
		visited = new boolean[point+1];
		bfs(start); 

		
	}
	public static void dfs(int start) {
		visited[start] = true;
		System.out.print(start+ " ");
		
		if(start == arr.length) {
			return;
		}

		for(int a=1;a<arr.length;a++) {
			if(arr[start][a] == 1 && visited[a] == false) {
				dfs(a);
			}
		}
			
	}
	public static void bfs(int start) {
		Queue<Integer> que = new LinkedList<Integer>(); 
		
		que.add(start);
		visited[start] = true;
 		System.out.print(start+ " ");
		
		while(!que.isEmpty()) {
			
			int temp = que.peek();
			que.poll();
			for(int i=1; i<arr.length;i++) {
				if(arr[temp][i] ==1 && visited[i] == false) {
					que.add(i);
					visited[i] = true;
					System.out.print(i+ " ");
				}
			}
		}
	}
	
	
	
}

---

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

1260번: DFS와 BFS