CS & Algorithm
[99클럽 코테 스터디] 6일차 TIL - 백준 1260번 DFS와 BFS
whatdoyumin
2025. 1. 20. 13:57
오늘의 문제는 백준 1260번 'DFS와 BFS'였다.
이 문제는 DFS와 BFS를 구현하는 간단한 문제다.
성공 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 1260 DFS와 BFS
public class Main {
static int[][] graph;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
static Queue<Integer> q = new LinkedList<>();
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());
graph = new int[N + 1][N + 1];
visited = new boolean[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a][b] = graph[b][a] = 1;
}
Dfs(V);
sb.append("\n");
visited = new boolean[N + 1];
Bfs(V);
System.out.println(sb.toString());
}
static void Dfs(int v) {
visited[v] = true;
// 재귀 사용
sb.append(v).append(" ");
for (int i = 0; i < graph.length; i++) {
if (graph[v][i] == 1 && !visited[i])
Dfs(i);
}
}
static void Bfs(int v) {
q.add(v);
visited[v] = true;
// 큐 사용
while (!q.isEmpty()) {
v = q.poll();
sb.append(v).append(" ");
for (int i = 0; i < graph.length; i++) {
if (graph[v][i] == 1 && !visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
}
문제 풀이에 앞서, 먼저 개념에 대해 살펴보겠다.
DFS (Depth - First Search)
DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
동작 과정
재귀 함수와 스택을 사용하는데, 재귀를 사용할 수 없을 때 스택을 사용한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
- 인접 노드가 모두 방문 처리가 되었다면 스택에서 최상단 노드를 꺼낸다.
- 즉, 매번 최상단 원소를 기준으로 방문하지 않은 인접 노드가 있으면 그 노드로 방문을 수행 (재귀 O)
- 위 과정을 할 수 없을 때까지 반복한다.
DFS를 사용하는 문제 유형
- 특정 경로를 찾는 문제
- 모든 노드를 방문해야 하는 문제
이러한 알고리즘이기 때문에, 위 코드에서 DFS에 대해
최상단 원소를 기준으로 재귀를 활용하여 구현했다.
BFS (Breadth-Fist Search)
BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
동작 과정
BFS는 큐 자료구조를 사용한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드이면서 방문 처리되지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- DFS와 달리 BFS는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다.
- 해당 시점에 큐의 첫 번째 요소가 기준이 된다.
- 위 과정을 할 수 없을 때까지 반복한다.
BFS를 사용하는 문제 유형
- 최단 경로를 구하는 경우
- 모든 간선의 가중치가 없거나 1일 경우
- 모든 간선의 가중치가 다를 경우 최단 경로를 구할 수 X
오늘의 회고
- DFS와 BFS의 개념을 다시 복기하느라 시간이 많이 지체된 것이 아쉽다.
- BFS를 구현할 때 큐를 사용하는 것이 익숙하지 않아서 인터넷에 검색을 해서 해결했다.
- DFS 함수를 불러온 뒤 BFS 함수를 불러오기 전에 visited를 초기화해주지 않아서 원하는 답이 나오지 않았었다.
- 실수 빈도가 많은 부분이 초기화 부분이다! 빠짐없이 확인하도록 해야겠다.