DFS/BFS 정리

DFS/BFS

🔍 개요

DFS (Depth-First Search, 깊이 우선 탐색)

• 특징 : 한 경로를 끝까지 파고든 후, 더 이상 갈 곳이 없으면 뒤로 돌아와 다른 경로 탐색
• 구현 : 재귀 함수 or 스택(Stack)
• 장점 : 구현 간단, 경로 탐색(백트래킹)에 유리.
• 단점 : 경로가 깊으면 스택 오버플로우 가능

BFS (Breadth-First Search, 넓이 우선 탐색)

• 특징 : 시작점에서 가까운 노드부터 차례대로 탐색
• 구현 : 큐(Queue)
• 장점 : 최단거리 문제에 자주 사용
• 단점 : 메모리 사용량 ↑

---

✅ DFS/BFS 공통 패턴

1. 그래프 표현

   • 인접 리스트 (List<List<Integer>>)
   • 인접 행렬 (int[][]) → 보통 N이 작을 때
   • 2D 배열 (격자 문제)

2. 방문 체크

   • boolean[] visited 또는 boolean[][] visited
   • 중복 방문 방지

3. 탐색 시작점

   • 연결 요소 문제 → 모든 정점 순회하며 방문 안 된 노드에서 시작
   • 특정 조건 → 문제에 따라 시작점/여러 개의 시작점 가능

4. BFS에서의 거리/단계 기록

   • dist[] 배열 또는 int[][] dist
   • 시작점 거리 = 0, 이후 dist[next] = dist[cur] + 1 → 최단거리

---

🤔 핵심 접근 방법

(A) DFS (재귀, 그래프)

class DFS {
	static List<List<Integer>> graph = new ArrayList<>();
	static boolean[] visited;
	
	public static void dfs(int v) {
		visited[v] = true;
		System.out.print(v + " "); // 방문 처리
		
		for(int next : graph.get(v)) {
			if(!visited[next]) {
				dfs(next);
			}
		}
	}
	
	public static void main(String[] args) {
        int n = 5;
        visited = new boolean[n+1];
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
 
        // 무방향 그래프 예시
        graph.get(1).add(2);
        graph.get(2).add(1);
        graph.get(1).add(3);
        graph.get(3).add(1);
        graph.get(2).add(4);
        graph.get(4).add(2);
        graph.get(3).add(5);
        graph.get(5).add(3);
 
        dfs(1); // 시작점 1
    }
}

(B) BFS (큐, 그래프)

class BFS {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
 
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.offer(start);
 
        while (!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur + " ");
 
            for (int next : graph.get(cur)) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int n = 5;
        visited = new boolean[n+1];
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(3).add(5);
 
        bfs(1);
    }
}

---

✅ 2차원 배열 탐색 예시

DFS (재귀)

int n, m;
int[][] map;
boolean[][] visited;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
 
void dfs(int x, int y) {
	visited[x][y] = true;
	for(int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx>=0 && ny>=0 && nx<n && ny<m && !visited[nx][ny] && map[nx][ny]==1) {
            dfs(nx, ny);
        }
	}
}

BFS(큐, 최단거리)

class Point {
	int x, y;
	
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
 
void bfs(int sx, int sy) {
	Queue<Point> q = new LinkedList<>();
	int[][] dist = new int[n][m];
	visited[sx][sy] = true;
	q.offer(new Point(sx, sy));
	dist[sx][sy] = 0;
	
	while(!q.isEmpty()) {
		Point cur = q.poll();
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx>=0 && ny>=0 && nx<n && ny<m && !visited[nx][ny] && map[nx][ny]==1) {
				visited[nx][ny] = true;
				dist[nx][ny] = dist[cur.x][cur.y] + 1;
				q.offer(new Point(nx, ny));
			}
		}
	}
}

---

❓ 대표 예시 문제

• DFS

  • 연결 요소 세기 (섬의 개수, 영역 개수)
  • 백트래킹 (N-Queen, 순열/조합 생성)

• BFS

  • 최단 거리 (미로 탐색, 숨바꼭질)
  • 다중 시작점 BFS (토마토, 불 퍼지기)

• 혼합

  • DFS로 영역 탐색 + BFS로 거리 계산 (안전 영역, 전염 시뮬레이션 등)