백준 : 1260 (DFS와 BFS)

 

이번문제는 가장 기본적인 DFS와 BFS문제인거 같다. 

 

여기서 주의해야 할점은

1. 방문할 수 있는 노드가 여러개이면, 작은 노드부터 방문한다 -> 정렬필요

2. 노드를 순서대로 출력 -> 방문표시시 출력한다.

3. DFS는 방문처리 1번, BFS는 방문처리 2번

 

import java.util.*;

class Main {

	static int n, m, s;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	static ArrayList<Integer> dfsList;
	static ArrayList<Integer> bfsList;

	public static void dfs(int now) {
		visited[now] = true; // 방문표시
		dfsList.add(now); // 출력(방문시만 출력*****)

		for (int i = 0; i < graph.get(now).size(); i++) {
			int tmp = graph.get(now).get(i);

			if (visited[tmp] == false) { // 아직 방문전
				dfs(tmp); // 재귀
			}
		}
	}
	
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>(); //큐
		q.offer(start); //삽입
		
		visited[start] = true; // 방문표시
		bfsList.add(start);//출력 
		
		while(!q.isEmpty()) {
			int now = q.poll(); //삭재
			
			for (int i = 0; i < graph.get(now).size(); i++) {
				int tmp = graph.get(now).get(i);

				if (visited[tmp] == false) { // 아직 방문전
					visited[tmp] = true; //방문표시
					bfsList.add(tmp); //출력
					
					q.offer(tmp); //삽입
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		s = sc.nextInt();
		sc.nextLine(); // 버퍼

		// 초기화
		visited = new boolean[n+1];
		graph = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < n+1; i++) { //인덱스 0제외 주의*****
			graph.add(new ArrayList<Integer>());
		}

		// 그래프입력
		for (int i = 0; i < m; i++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			int a = Integer.parseInt(stArr[0]);
			int b = Integer.parseInt(stArr[1]);

			graph.get(a).add(b);
			graph.get(b).add(a); // 양방향그래프*****
		}

		for (int i = 0; i < n+1; i++) { //작은순으로 정렬
			Collections.sort(graph.get(i));
		}
		
		//DFS
		dfsList = new ArrayList<Integer>();
		dfs(s);
		
		visited = new boolean[n+1]; //초기화
		
		//BFS
		bfsList = new ArrayList<Integer>();
		bfs(s);
		
		//출력
		for (int i = 0; i < dfsList.size(); i++) {
			System.out.print(dfsList.get(i) + " ");
		}
		
		System.out.println();
		
		for (int i = 0; i < bfsList.size(); i++) {
			System.out.print(bfsList.get(i) + " ");
		}
	}
}