[백준(Baekjoon)] 1260. DFS와 BFS

 

 

[백준(Baekjoon)] 1260. DFS와 BFS

 

 

1260번: DFS와 BFS

 

 

 

[입력]

 

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

 

[출력]

 

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

[풀이]

 

깊이우선탐색(DFS)와 너비우선탐색(BFS)문제이다.

DFS는 방금 방문한 정점 기준으로 계속 간선을 찾기 때문에 스택과 재귀를 사용했다.

둘 다 큐나 스택에 넣고 방문 표시하고 미방문 연결 간선을 찾는 것은 같다.

그러나 DFS는 매개변수의 현재정점 current를 이용하고 간선 찾을 시에 재귀로 다시 연결된 간선을 찾은 후,

이 과정이 완료되면 pop하여 스택에 있는 현재정점을 삭제한다. 

그럼 연결된 간선이 없다는 걸 알면 스택 pop하고 그 전 정점에 연결된 정점으로 가서 간선을 찾게된다.

 

 

[코드]

 

public class bj1260 {

	static int N,M,V;
	static int arr[][];
	static boolean isVisited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		arr = new int[N+1][N+1];
		isVisited = new boolean[N+1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x][y] = arr[y][x] = 1;
		}
		
		dfs(V);
		System.out.println();
		bfs();
	}
	
	private static void dfs(int current){ //현재정점
		Stack<Integer> s = new Stack<>();
		s.push(current); //현재정점 스택에 넣고 방문 표시
		isVisited[current] = true;
		System.out.print(current + " ");
		
		while(!s.isEmpty()) {
			for (int i = 1; i <= N; i++) {
            //현재정점과의 간선이 있고 방문하지 않았으면 방문표시 후 스택에 추가
				if(!isVisited[i] && arr[current][i] == 1) {
					s.push(i);
					isVisited[i] = true;
					dfs(i); //방금 방문한 정점 기준으로 다시 간선 찾기
				}
			}
			s.pop(); //방문 완료하고 오면 pop해주기
		}
		
	}
	
	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		isVisited = new boolean[N+1];
		isVisited[V] = true;
		q.offer(V); //큐에 시작정점 넣기
		
		while(!q.isEmpty()) {
			int current = q.poll(); //정점 빼서 출력후 간선찾기
			System.out.print(current + " ");
			for (int i = 1; i <= N; i++) {
				if(!isVisited[i] && arr[current][i] == 1) {
					isVisited[i] = true;
					q.offer(i); //간선 있으면 방문표시 후 큐에 넣기
				}
			}
		}
	}

}