BJ1260 DFS와 BFS

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

DFS 깊이우선탐색과 BFS 너비우선탐색을 알고 구현할 수 있는지를 묻는 문제다.

입력 받은 값으로 인접행렬을 만든 후에
BFS를 Queue로 구현하고, DFS를 재귀함수로 구현하면 된다.

package day0221;

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

/*7
8 1
0 1
0 2
1 3
1 4
2 4
3 5
4 5
5 6
*/
public class BFSDFS {
	static int N;
	
	public static void bfs(int[][] adjMatrix, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		queue.offer(start);
		visited[start] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.print(current+1 + " ");
			
			// current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
			for(int j = 0; j < N; j++) {
				if(!visited[j] && adjMatrix[current][j] > 0) {
					queue.offer(j);
					visited[j] = true;
				}
			}
		}
	}
	
	public static void dfs(int[][] adjMatrix, boolean[] visited, int current) {
		
		visited[current] = true;
		System.out.print(current+1 + " ");

		// current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
		
		for(int j = 0; j < N; j++) {
			if(!visited[j] && adjMatrix[current][j] > 0) {
				dfs(adjMatrix, visited, j);
			}
		}
		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int C = sc.nextInt();
		int V = sc.nextInt();		
		int[][] adjMatrix = new int[N][N];
		
		for(int i = 0; i < C; i++) {
			int from = sc.nextInt() - 1;
			int to = sc.nextInt() - 1;
			adjMatrix[from][to] = 1;
			adjMatrix[to][from] = 1;
		}
		
	/*	for(int[] is : adjMatrix) {
			System.out.println(Arrays.toString(is));
		}*/
		dfs(adjMatrix, new boolean[N], V - 1);
		System.out.println();
		bfs(adjMatrix, V - 1);
		
	
	}
}

좋은 웹페이지 즐겨찾기