백준 - DFS와 BFS[java]
문제출처: https://www.acmicpc.net/problem/1260
문제 설명
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력 예시
5 5 3
5 4
5 2
1 2
3 4
3 1
출력 예시
3 1 2 5 4
3 1 4 2 5
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
HashSet<Integer> hs = new HashSet<>();
StringBuilder sb = new StringBuilder();
st.nextToken();
int vertices = Integer.parseInt(st.nextToken());
int startVertex = Integer.parseInt(st.nextToken());
while (vertices-- > 0) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
ArrayList<Integer> connected = hm.containsKey(start) ? hm.get(start) : new ArrayList<>();
connected.add(end);
hm.put(start, connected);
connected = hm.containsKey(end) ? hm.get(end) : new ArrayList<>();
connected.add(start);
hm.put(end, connected);
}
Queue<Integer> q = new LinkedList<>();
q.add(startVertex);
hs.add(startVertex);
sb.append(startVertex).append(" ");
BFS(q, hs, hm, sb);
hs.clear();
hs.add(startVertex);
System.out.print(startVertex + " ");
DFS(hm, startVertex, hs);
System.out.println();
System.out.println(sb);
br.close();
String i = "software engineering";
}
public static void DFS(HashMap<Integer, ArrayList<Integer>> hm, int startingVertex, HashSet<Integer> hs) {
if (hm.get(startingVertex) != null) {
for (int vertex : hm.get(startingVertex)) {
if (!hs.contains(vertex)) {
hs.add(vertex);
System.out.print(vertex + " ");
} else
continue;
DFS(hm, vertex, hs);
}
}
}
public static void BFS(Queue<Integer> q, HashSet<Integer> hs, HashMap<Integer, ArrayList<Integer>> hm, StringBuilder sb) {
while (!q.isEmpty()) {
int vertex = q.poll();
ArrayList<Integer> al = hm.get(vertex);
if (al != null) {
Collections.sort(al);
for (int v : al) {
if (!hs.contains(v)) {
hs.add(v);
q.add(v);
sb.append(v).append(" ");
}
}
}
}
}
}
입력값을 받아서 HashMap<Integer, ArrayList> 형태로 그래프를 생성하였다.
DFS는 재귀 함수를 사용하였고, BFS는 큐를 사용하여 풀었다.
방문한 노드는 해쉬셋을 사용하여 확인을 하였다.
Author And Source
이 문제에 관하여(백준 - DFS와 BFS[java]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@davidko/백준-DFS와-BFSjava저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)