#1260 : DFS와 BFS

풀이방법

사용된 것:

깊이우선탐색(DFS)

너비우선탐색(BFS)

스택(Stack)

큐(Queue)

 

2022.06.01

기본적인 DFS와 BFS를 둘 다 사용해보는 스탠다드 문제이다.

스택을 이용해 DFS를 해주고, 큐를 이용해 BFS를 해주었다.

단, 방문할 수 있는 노드가 여러 개 있을 때엔 노드의 번호의 크기가 작은 것부터 방문한다는 점에 주의해야 한다. 이 때문에 스택에는 자식노드들을 내림차순으로 넣어주고, 큐에는 오름차순으로 넣어주었다. 인접 리스트의 내용물의 정렬은 TreeSet의 자동 오름차순 정렬과 desceningSet 기능을 이용하여 해결했다.

 

코드

Java(2022.06.01)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());
		//간선정보 읽어와 저장하기
		//인접노드 리스트가 오름차순 정렬된 간선정보 배열
		TreeSet<Integer>[] ascending = new TreeSet[n+1];
		for(int i=1; i<n+1; i++) ascending[i] = new TreeSet<Integer>();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			ascending[a].add(b);
			ascending[b].add(a);
		}
		//인접노드 리스트가 내림차순 정렬된 간선정보 배열
		NavigableSet<Integer>[] descending = new NavigableSet[n+1];
		for(int i=1; i<n+1; i++) descending[i] = ascending[i].descendingSet();
		
		//DFS 수행
		boolean[] visited = new boolean[n+1];
		ArrayList<Integer> dfs = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();
		stack.add(v);
		while(!stack.isEmpty()) {
			//top의 정점이 이미 방문한 놈이라면 그냥 갖다버리고 continue
			if(visited[stack.peek()]) {stack.pop(); continue;}
			//top의 정점이 아직 방문하지 않은 놈이라면 아래를 수행
			int cur = stack.pop();	//스택에서 꺼내기
			dfs.add(cur);	//출력할 정답에 추가
			visited[cur] = true;	//방문했다고 표시
			for(int i: descending[cur]) {	//모든 자식을 스택에 넣기(내림차순으로)
				stack.add(i);
			}
		}
		//DFS 결과값 출력
		for(int i:dfs) System.out.print(i+" ");
		System.out.println();
		
		
		//BFS 수행
		Arrays.fill(visited, false);
		ArrayList<Integer> bfs = new ArrayList<Integer>();
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v);
		while(!queue.isEmpty()) {
			//가장 앞의 정점이 이미 방문한 놈이라면 갖다버리고 continue
			if(visited[queue.peek()]) {queue.poll(); continue;}
			//가장 앞의 정점이 아직 방문하지 않은 놈이라면 아래를 수행
			int cur = queue.poll();	//큐에서 꺼내기
			bfs.add(cur);	//출력할 정답에 추가
			visited[cur] = true;	//방문했다고 표시
			for(int i: ascending[cur]) {	//모든 자식을 스택에 넣기(오름차순으로)
				queue.add(i);
			}
		}
		
		//BFS 결과값 출력
		for(int i:bfs) System.out.print(i+" ");

	}

}