백준 1260, DFS와 BFS - DFS & BFS
https://www.acmicpc.net/problem/1260
1. 아이디어
-
입력 그래프를 n x n 인접 행렬에 저장 (n: 정점 vertex 개수)
=> 대각 행렬 형태로 저장 e.g. [1][3] 연결되면 [3][1]도 연결
1) DFS
- 재귀함수
- 재귀함수 종료 조건: 매 재귀에서 시작 vertex에 연결된 vertex가 없거나,
시작 정점으로부터 연결된 모든 vertex를 이미 방문한 경우
<=> 탐색 더 수행해야하는 경우: 시작 정점으로부터 연결된 vertex가 존재하고, 연결된 vertex를 아직 방문 안한 경우
2) BFS
- Queue
- Queue에 시작 vertex를 추가, Queue가 empty 할 때까지 반복
① Queue에서 vertex를 하나 꺼냄
② 꺼낸 vertex와 연결된 vertex가 존재하고 해당 연결된 vertex를 방문 안한 경우,
해당 연결된 vertex를 Queue에 추가다음 차례에 탐색할 vertex를 Queue에 추가하면서, 방문 처리 할 것
2. 자료구조
boolean[][]
: 그래프 (인접 행렬 형태로 저장)boolean[]
: vertex 방문 확인Queue<Integer>
: BFS
3. 시간 복잡도
- DFS와 BFS의 시간 복잡도 = O(V + E) (V: vertex 개수, E: edge 개수)
=> O(N + M)에 N, M 최대값 대입 => O(1,000 + 10,000) = O(11,000) << 2억 (2초)
코드
import java.io.*;
import java.util.*;
public class Main {
static int n, m, v; // n: 정점 vertex 개수, m: 간선 edge 개수, v: 탐색 시작 vertex 번호
static boolean[][] graph; // 그래프 (인접 행렬 형태로 저장)
static boolean[] check; // 정점 방문 확인
static void dfs(int start) {
check[start] = true;
System.out.print(start + " ");
for (int i = 1; i <= n; i++) {
// 연결되어 있고 아직 방문 안한 vertex 가 존재하면, 더 탐색
if (graph[start][i] && !check[i])
dfs(i);
}
}
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start); // Queue에 vertex 추가하고, 방문 처리
check[start] = true;
System.out.print(start + " ");
while (!queue.isEmpty()) {
start = queue.remove();
for (int i = 1; i <= n; i++) {
if (graph[start][i] && !check[i]) {
queue.add(i);
check[i] = true;
System.out.print(i + " ");
}
}
}
}
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()); // 정점 vertex 개수
m = Integer.parseInt(st.nextToken()); // 간선 edge 개수
v = Integer.parseInt(st.nextToken()); // 탐색 시작 정점 vertex 번호
graph = new boolean[n + 1][n + 1]; // [1 ~ n][1 ~ n] 사용
check = new boolean[n + 1]; // [1 ~ n] 사용
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph[start][end] = true;
graph[end][start] = true;
}
System.out.println();
System.out.print("DFS: ");
dfs(v);
System.out.println();
check = new boolean[n + 1]; // 방문 확인 배열 초기화
System.out.print("BFS: ");
bfs(v);
}
}
Author And Source
이 문제에 관하여(백준 1260, DFS와 BFS - DFS & BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)