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);
}
}
Author And Source
이 문제에 관하여(BJ1260 DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ1260-DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)