[ 백준 1260 ] DFS 와 BFS - JAVA

문제 링크

http://boj.kr/1260

1260번: DFS와 BFS

문제 풀이

DFS와 BFS를 공부하기 위해서 꼭 한번 풀어볼 만한 기본적인 문제이다.

 

소스 코드

import java.util.LinkedList;
import java.util.Scanner;

class Graph{
	int V;
	public LinkedList<Integer> adj [] ; //
	public Graph(int v) {
		V = v;
		adj = new LinkedList [v+1];
		for (int i = 0; i < v+1; i++) {
			adj[i] = new LinkedList<>();
		}
	}

	void add(int v ,int w) {
		adj[v].add(w);
		adj[w].add(v);
	}

	void dfs(int v, boolean [] isVisited) {
		isVisited[v] = true;
		System.out.print(v+" ");

		for (int i = 0; i < adj[v].size(); i++) {
			int w = adj[v].get(i);
			if(!isVisited[w]) {
				dfs(w, isVisited);
			}
		}
	}

	void bfs(int v) {
		boolean[] isVisited = new boolean[V+1];

		LinkedList<Integer> que = new LinkedList<>();
		que.add(v);
		isVisited[v] = true;
		while(!que.isEmpty()) {
			int w = que.poll();
			System.out.print(w+" ");
			for (int i = 0; i < adj[w].size(); i++) {
				int x = adj[w].get(i);
				if(!isVisited[x]) {
					isVisited[x] = true;
					que.add(x);
				}
			}
		}
	}


}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N= sc.nextInt();
		int M = sc.nextInt();
		int V = sc.nextInt();

		Graph gr = new Graph(N);

		for (int i = 0; i < M; i++) {
			gr.add(sc.nextInt(), sc.nextInt());
		}
		for (LinkedList list : gr.adj) {
			list.sort(null);
		}
		gr.dfs(V, new boolean[N+1]);
		System.out.println();
		gr.bfs(V);
	}
}