백준 BaekJoon 1260번: DFS와BFS [Java]

2021-03-05

---

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

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

출력

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

---

소스코드

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class TemplateA {	
	static int nV; // 정점의 수
	static int nE; // 간선의 수
	static int [][] arr2d; 
	//간선간의 위치를 저장할 2차원 배열
	static boolean [] checkDFS;
	static boolean [] checkBFS;
	//방문정점을 체크할 배열 두개 사용하기 때문에 두개 선언

	// dfs 정렬 메서드
	static void dfs(int i) {
		System.out.print(i + " ");
		//방문한 정점 출력
		checkDFS[i] = true;
		//해당 정점 방문했으니까 체크;

		for(int j = 1; j < nV + 1; j++) {
			if(arr2d[i][j] == 1 && checkDFS[j] == false) {
				// 정점사이 간선이 연결되어 있고 다음에 방문할
				// 정점이 미방문 정점이라면 다음 깊이를 탐색
				dfs(j);
			}
		}
	}

	//	bfs 정렬 메서드
	static void bfs(int i) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(i);

		while(!q.isEmpty()) {
			int temp = q.poll();
			//loop를 들면서 큐에 들을 정점을 순서대로 하나씩 추출함
			// 선입 선출을 법칙
			System.out.print(temp + " ");
			checkBFS[temp] = true;
			//해당 정점 방문했으니까 체크;

			for(int j = 1; j < nV + 1; j++) {
				if(arr2d[temp][j] == 1 && checkBFS[j] == false) {
					q.offer(j);
					// 인접한 정점이 있으면 큐에 넣어줌
					checkBFS[j] = true;
					//해당 정점 방문했으니까 체크;
				}
			}
		}
	}
	//////////////////////////////////////////////////////////	
	// 메인메서드 시작 - > 실행 영역
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		nV = scan.nextInt();
		nE = scan.nextInt();
		int start = scan.nextInt();
		arr2d = new int [nV + 1][nV + 1];
		checkDFS = new boolean [nV + 1];
		checkBFS = new boolean [nV + 1];
		// 0부터 시작이 아닌 1부터 체크하기 때문에 모두 +1을 해준다.

		for(int i = 0; i < nE; i++) {
			int temp1 = scan.nextInt();
			int temp2 = scan.nextInt();

			arr2d[temp1][temp2] = arr2d[temp2][temp1] = 1;
			// 간선은 양방향 이기 때문에 두 배열위치모두 같이 변경해야한다.
		}
		
		dfs(start);
		System.out.println();
		bfs(start);
		
		
	}
}

 

출처링크 : www.acmicpc.net/problem/1260

1260번: DFS와 BFS