[JAVA] DFS와 BFS_1260

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

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

출력

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

예제 입력 1 복사

 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: dfghcvb11, djm03178, doju
• 어색한 표현을 찾은 사람: doju
• 빠진 조건을 찾은 사람: pumpyboom

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

DFS와 BFS

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);

		int n = s.nextInt(); // 정점의 갯수
		int m = s.nextInt(); // 간선의 갯수
		int v = s.nextInt(); // 출발점

		int[][] graph = new int[n + 1][n + 1]; // 그래프 구성

		for (int i = 0; i < m; i++) {
			int startNode = s.nextInt();
			int endNode = s.nextInt();

			graph[startNode][endNode] = 1;
			graph[endNode][startNode] = 1;
		}

		Boolean[] isVisited = new Boolean[n + 1]; // 방문 여부 확인
		Arrays.fill(isVisited, false); // false로 초기화

		DFS(n, v, graph, isVisited); // 노드 수, 시작점, 그래프, 방문여부
		System.out.println();

		Arrays.fill(isVisited, false); // 다시 초기화
		BFS(n, v, graph, isVisited); // 노드 수, 시작점, 그래프, 방문여부

	}

	public static void BFS(int n, int node, int[][] graph, Boolean[] isVisited) {
		// 순서대로 진행하기 위해 순서 저장
		Queue<Integer> queue = new LinkedList<>();
		// 첫 시작 노드 기록
		queue.offer(node);
		isVisited[node] = true;

		while (!queue.isEmpty()) {
			int tmp = queue.poll(); // 현재 위치 값 빼오기
			System.out.print(tmp + " ");

			for (int i = 1; i < n + 1; i++) {
				if (graph[i][tmp] == 1 && !isVisited[i]) {
					// 경로가 있고 방문한 적이 없으면 진행
					queue.offer(i);
					isVisited[i] = true;
				}
			}
		}
	}
    
	public static void DFS(int n, int node, int[][] graph, Boolean[] isVisited) {
		// 방문한 사실 기록
		isVisited[node] = true;
		System.out.print(node + " ");

		for (int i = 1; i < n + 1; i++) {
			if (graph[i][node] == 1 && !isVisited[i]) {
				// 경로가 있고 방문한 적이 없으면 진행
				DFS(n, i, graph, isVisited);
			}
		}
	}
}