백준 JAVA11 1260번 : DFS와 BFS 프로그램

Mention : DFS는 Stack🥞 BFS는 Queue👯👫

DFS와 BFS

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	210731	78135	46407	36.048%

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 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

슈도 코드

N(노드의 개수)
M(엣지의 개수)
visited(방문한 노드 기록)
V(탐색을 시작할 노드의 번호)
s(엣지가 연결하는 노드 번호 시작)
e(엣지가 연결하는 노드 번호 끝)

for(N만큼) {
	 A인접 리스트의 각 ArrayList 초기화 
}
for(M만큼) {
	인접리스트 그래프데이터에 저장
	add(e,s)
	add(s,e)
}
DFS 구현하기
for(i :) {
	if(방문하지 않은 노드) {
		DFS 함수	
	}
}
BFS 구현하기
	큐 자료구조 사용
	큐 자료구조에 시작 노드 삽입하기(add)
	visited 배열에 현재 노드 방문 기록하기
	while(큐가 비어있을 때 까지) {
		큐에서 노드 데이터를 가져오기(poll)
		가져온 노드 출력
		for(i :) {
			현재 노드의 연결 노드 중 미방문 노드를 큐에 삽입(add)
			방문 배열에 기록
		}
	}
}

DFS 출력
BFS 출력

DFS 함수 구현 (재귀함수)
BFS 함수 구현 (큐로)

Code

package dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P1260_dfs_bfs {
	static boolean[] visited;
	static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		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());

		A = new ArrayList[N + 1];

		for (int i = 1; i <= N; i++) {
			A[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			A[e].add(s);
			A[s].add(e);
		}

		for (int i = 1; i <= N; i++) {
			Collections.sort(A[i]);
		}

		visited = new boolean[N + 1];
		DFS(V);
		System.out.println();

		visited = new boolean[N + 1];
		BFS(V);
		System.out.println();
	}
	
	private static void DFS(int v) {
		System.out.print(v + " ");
		visited[v] = true;
		for (int i : A[v]) {
			if (visited[i] == false) {
				DFS(i);
			}
		}
	}

	private static void BFS(int v) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v);
		visited[v] = true;

		while (!queue.isEmpty()) {
			int now_Node = queue.poll();
			System.out.print(now_Node + " ");
			for (int i : A[now_Node]) {
				if (!visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}
}