[백준] DFS와 BFS

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;



public class Main {
	static Node[] arr;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N =sc.nextInt();
		int M =sc.nextInt();
		int V= sc.nextInt();
		
		arr = new Node[N+1];
		
		for(int i=0;i<=N;i++) {
			arr[i] = new Node(i); 
		}
		//인접리스트만들기.
		for(int i=0;i<M;i++) {
			Node fir =arr[sc.nextInt()];
			Node sec =arr[sc.nextInt()];
			if(!fir.adj.contains(sec)) 	fir.adj.add(sec);
			if(!sec.adj.contains(fir)) 	sec.adj.add(fir);
		}
		//정렬하기
		for(int i=1;i<=N;i++) { 
			Collections.sort(arr[i].adj,new Comparator<Node>() {
			 @Override public int compare(Node N1, Node N2) { 
			  if(N1.node < N2.node) return -1; 
			  else if(N1.node > N2.node) return 1;
			  return 0; } 
		  }); 
		}
		 
		DFSRecur(V);
		for(int i=0;i<=N;i++) {
			arr[i].check=false; 
		}
		BFS(V);
	}
	
	static void DFSRecur(int start) {
		Node r = arr[start];
		System.out.print(r.node+" ");
		r.check =true;
		for(int i=0;i<r.adj.size();i++) {
			int k =  r.adj.get(i).node;
			if(arr[k].check==false) {
				DFSRecur(k);
			}
		}
	}
	
	static void DFS(int start) {
		Node root = arr[start];
		Stack<Node> stack = new Stack<Node>();
		stack.add(root);
		root.check = true;
		while(!stack.isEmpty()) {
			Node ano =  stack.pop();
			for(Node n : ano.adj) {
				if(n.check==false) {
					n.check=true;
					stack.push(n);
					break;
				}
			}
			System.out.print(ano.node+" ");
		}
	}
	static void BFS(int start) {
		System.out.println();
		Node root = arr[start];
		Queue<Node> que = new LinkedList<Node>();
		que.offer(root);
		root.check  = true;
		while(!que.isEmpty()) {
			Node ano = que.poll();
			for(Node n:ano.adj) {
				if(n.check==false) {
					n.check =true;
					que.add(n);
				}
			}
			System.out.print(ano.node+" ");
		}
		
	}
}
class Node{
	int node;
	ArrayList<Node> adj;
	boolean check;
	Node(int node){
		this.node =node;
		this.check =false;
		adj =  new ArrayList<Node>();
	}
}

DFS BFS를 공부를 안하다 보니 다 잊었다...

다시 공부하자..

 

Node클래스를 만들어서 구현했지만.

다음번에는 그냥 ArrayList 배열을 사용해서 해보면 좋을 것 같다.!

 

DFS는 재귀로도 구현해보았고, stack자료구조를 이용해서도 진행해보았다. 

 

알고리즘은 꾸준히 해주는게 확실히 좋은 거 같다..