[Eric's 백준] 1260번 - DFS 와 BFS - Java

안녕하세요! Eric 입니다

오늘은 그래프 순회 문제를 풀어보도록 하겠습니다.

dfs 랑 bfs 를

주어진 예시를 바탕으로 

저는 직접 그려서 문제를 풀어 보았습니다.

하단의 두 사진 중 각각좌측 부분의 그림이 dfs 방식이며,

하단의 두 사진 중 각각 우측 부분이 Queue를 이용한 bfs 방식입니다.

 

 

 

코드구현

코드를 구현해보았습니다.

	import java.io.*;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	class N1260 {
	static boolean[][] graph;
	static boolean[] visited;
	static int n, m, v;
	static Queue<Integer> Q = new LinkedList<>();
	public static void main(String[] args) throws IOException {
	// 0. 입력 및 초기화
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	v = Integer.parseInt(st.nextToken());
	// 1. 그래프 정보 입력
	graph = new boolean[n + 1][n + 1];
	visited = new boolean[n + 1];
	int x, y;
	for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
	x = Integer.parseInt(st.nextToken());
	y = Integer.parseInt(st.nextToken());
	graph[x][y] = graph[y][x] = true;
	}
	// 2. dfs 및 결과 출력
	dfs(v);
	System.out.println();
	visited = new boolean[n + 1];
	// 3. bfs 및 결과 출력
	bfs(v);
	br.close();
	}
	public static void dfs(int idx) {
	visited[idx] = true;
	System.out.print(idx + " ");
	for (int i = 1; i <= n; i++) {
	if (!visited[i] && graph[idx][i]) {
	dfs(i);
	}
	}
	}
	public static void bfs(int idx) {
	Q.offer(idx);
	visited[idx] = true;
	while (!Q.isEmpty()) {
	idx = Q.poll();
	System.out.print(idx + " ");
	for (int i = 1; i <= n; i++) {
	if (!visited[i] && graph[idx][i]) {
	Q.offer(i);
	visited[i] = true;
	}
	}
	}
	}
	}

view raw N1260.java hosted with ❤ by GitHub