[백준1260] DFS와 BFS

DFS와 BFS를 출력하는 가장 기초적인 문제입니당

---

메인부분

public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int dot = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		Vertex[] v = new Vertex[dot+1];
		for(int i=0; i<v.length; i++) {
			v[i] = new Vertex();
		}
		
		int a = 0;
		int b = 0;
		for(int i=0; i<edge; i++) {
			st = new StringTokenizer(br.readLine());
			
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			v[a].al.add(b);
			v[b].al.add(a);
		}
		
		for(int i=0; i<v.length; i++) {
			if(v[i].al.size()!=0) {
				Collections.sort(v[i].al);
			}
		}
		
		DFS(v, start);
		clear(v);
		System.out.println("");
		BFS(v, start);
	}

코드는 지저분합니다....

일단 입력형식대로 받아 길이에 맞게 Vertex 배열을 생성해줬는데,

입력받은대로 배열을 생성하면 길이처리가 귀찮아서 그냥 +1 해서 생성해줬습니다.

그리고 간선갯수만큼 돌리며 이어져있다는 것을 적었고,

DFS부분 처리를 위해 이어져있는 노드를 정렬했습니다.

Vertex 

class Vertex{
	int visit;  // 0: not visited,  1: visited
	ArrayList<Integer> al;
	
	public Vertex() {
		visit = 0;
		al = new ArrayList<Integer>();
	}
}

Vertex부분은 그냥 간단히 했어요 

visit변수는 주석 적힌대로 방문 유무,

어레이리스트는 연결된거 넣어줄라구.

DFS

public static void DFS(Vertex[] v, int start) {
	v[start].visit = 1;
	System.out.print(start+" ");
	
	int next = 0;
	for(int i=0; i<v[start].al.size(); i++) {
		next = v[start].al.get(i);
		
		if(v[next].visit==0) {
			DFS(v, next);
		}
	}
}

재귀로 구현

DFS 같은 경우 스타트부터 시작해 

연결된 노드를 하나씩 가져오며 (sort를 사용해 순서대로 정렬되있음) 

방문하지 않았으면 그걸 가지고 다시 DFS반복...

BFS

public static void BFS(Vertex[] v, int start) {
	Queue<Integer> q = new LinkedList<Integer>();
	q.add(start);
	v[start].visit = 1;
		
	int temp = 0;
	while(!q.isEmpty()) {
		temp = q.poll();
		System.out.print(temp+" ");
		
		int next = 0;
		for(int i=0; i<v[temp].al.size(); i++) {
			next = v[temp].al.get(i);
			if(v[next].visit==0) {
				v[next].visit = 1;
				q.add(next);
			}
		}
	}
}

BFS는 큐를 사용해 스타트 하는 부분을 넣고

큐가 빌때까지 while문을 돌리며 

큐에서 하나 가져오고 가져온 노드의 인접노드를 다 가져오면서

인접노드가 방문하지 않았다면 큐에 넣었습니다.

코드 짜는 수준은 지저분해용 일단 문제 통과가 우선순위가 높아서.

다른 자료 안찾아보고 그냥 기억더듬으며 한거에 의의를...