[백준 1260] DFS와 BFS - 자바

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

1260번: DFS와 BFS

 

1. 풀이

---

이 문제는 DFS와 BFS의 구현을 하는 문제입니다.

 

그래프를 구성하는 방법은 인접 리스트와 인접 행렬이 있습니다. 

 

둘 중 아무거나 선택해서 구현을 하면 되지만, 저는 인접 행렬을 통해서 구현했습니다.

 

주의할 점은 DFS에서 스택을 통한 구현과, 재귀를 통한 구현이 있는데요.

 

이 문제에서의 DFS는 재귀를 통한 방식의 방문을 하므로, 재귀를 통해 풀어야합니다. ( 물론 스택을 통한 방법도 있을겁니다. )

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int V; // vertex
	static int E; // Edge
	static boolean[] visited;
	static int[][] graph;
	static int startPoint;
	
	static void dfs(int index) {
		if(visited[index] == true)
			return;
		else
			visited[index] = true;
		System.out.print(index+" ");
		
		for(int i = 1; i <= V; i++) {
			if(graph[index][i] == 1 && visited[i] != true) {
				dfs(i);
			}
		}
	}
	
	static void bfs(int index) {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[index] = true;
		queue.offer(index);
		System.out.print(index+" ");
		
		int tmp;
		while(!queue.isEmpty()) {
			tmp = queue.poll();
			for(int i = 0; i < V+1; i++) {
				if(graph[tmp][i] == 1 && visited[i] != true) {
					queue.offer(i);
					visited[i] = true;
					System.out.print(i+" ");
				}
			}
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		graph = new int[1001][1001];
		visited = new boolean[10001];
		V = sc.nextInt();
		E = sc.nextInt();
		startPoint = sc.nextInt();
		
        // 간선 연결
		int a,b;
		for(int i = 0; i < E; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			
			graph[a][b] = graph[b][a] = 1;
		}
		
		dfs(startPoint); // dfs
		
		// visit 초기화
		for(int i = 0; i <= V; i++)
			visited[i] = false;
		System.out.println();
		
		bfs(startPoint); // bfs
		
		sc.close();
		return;
	}
}