개요
아래 내용은 DFS/BFS의 핵심 개념을 먼저 정리한 뒤, A2dfs, A3bfs 패키지에 있는 실습 코드(방문 순서 + BFS 최단거리)를 통해 “인접 리스트 설계 → 방문 처리 위치 → 탐색 결과가 달라지는 포인트”를 한 흐름으로 정리한 글이다.
DFS(깊이 우선 탐색)
DFS는 현재 정점에서 갈 수 있는 경로를 깊이 방향으로 끝까지 파고드는 탐색 방식이다.
더 이상 진행할 수 없으면(갈 수 있는 미방문 인접 정점이 없으면) 마지막 갈림길이 있던 정점으로 되돌아가 다른 경로를 탐색한다
DFS 탐색 절차(일반 흐름)
- 시작 노드 방문 처리
- 시작 노드의 “방문하지 않은 인접 노드” 중 조건(예: 번호가 작은 순)으로 하나를 선택해 이동.
- 이동한 노드에서도 같은 과정을 반복하고, 더 이상 갈 곳이 없으면 호출이 끝나며 되돌아감.
DFS 구현 포인트
- 구현은 보통 재귀 함수 또는 스택으로 한다
- “모든 경우의 수를 탐색”해야 하는 문제(완전 탐색 성격)에 자주 어울린다.
DFS 확장: 2차원 완전 탐색 (A02이차원배열의완전탐색)
2차원 지도/격자 문제는 보통 int[][] 같은 2차원 배열로 주어지고, “갈 수 있음/없음/시작/도착” 같은 상태가 숫자로 표현된다
이때 DFS는 한 칸에서 시작해서 인접한 칸으로 계속 들어가며, 연결된 영역을 끝까지 훑는 방식으로 자주 사용된다
상하좌우 이동을 dx/dy로 관리
격자 탐색에서는 상하좌우(또는 대각선 포함) 이동을 dx, dy 배열로 관리하면 방향 케이스를 반복문 하나로 통일할 수 있다.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};(중요) 이 코드에서 보완해야 할 점
지금 올려준 A02이차원배열의완전탐색은 방문 체크(visited)가 없어서 같은 칸을 무한히 재방문하며 재귀가 끝나지 않을 수 있다.
실전 문제에서는 boolean[][] visited를 두고 “재귀 진입 직후 방문 처리”를 해서 사이클을 차단하는 형태로 바꾸는 게 안전하다.
BFS(너비 우선 탐색)
BFS는 현재 정점에서 인접한 노드들을 가까운 순서(레벨 순서) 로 탐색하는 방식이다.
큐(Queue)의 FIFO 특성 때문에 “깊이 0 → 깊이 1 → 깊이 2 …” 순으로 넓게 퍼져나간다.
BFS 탐색 절차(일반 흐름)
- 시작 노드를 먼저 방문 처리
- 시작 노드의 미방문 인접 노드를 큐에 넣음
- 큐에서 하나 꺼내고, 그 노드의 미방문 인접 노드를 다시 큐에 넣음(큐가 빌 때까지 반복).
BFS가 거리 문제에 강한 이유
가중치가 없는 그래프(한 번 이동 비용이 동일)에서는 BFS가 레벨 순으로 확장되기 때문에, 어떤 정점에 “처음 도착했을 때의 거리”가 최단거리로 해석되는 경우가 많다.
그래서 최단거리, 시작점으로부터의 거리 측정 같은 문제에 잘 맞는다.
실습 공통 준비: 인접 리스트로 그래프 만들기
세 코드 모두 int[][] nodes 형태의 간선 목록을 인접 리스트(adjList) 로 바꿔서 탐색한다.
인접 리스트는 adjList.get(정점)으로 바로 이웃 정점 목록을 얻을 수 있어 탐색에 유리하다.
무방향(양방향) 그래프 처리
실습 코드에서는 간선을 읽을 때 아래처럼 양쪽에 모두 추가한다
adjList.get(n[0]).add(n[1]);
adjList.get(n[1]).add(n[0]);방문 순서 조건(번호 작은 것부터)
문제/실습에서 “정점 번호가 작은 것부터 방문” 규칙을 넣기 위해, 각 정점의 인접 리스트를 오름차순 정렬한다
for (List<Integer> l : adjList) {
l.sort(Comparator.naturalOrder());
}DFS 방문 순서 실습: A01Dfs방문순서
코드 구조 요약
adjList: 인접 리스트visited: 방문 여부 배열dfs(0)부터 시작
핵심 로직
static void dfs(int start) {
System.out.println(start);
visited[start] = true;
for (int target : adjList.get(start)) {
if (!visited[target]) {
dfs(target);
}
}
}이 코드에서 관찰할 포인트
System.out.println(start)가 방문 시점 출력이므로, 출력 순서가 곧 DFS 방문 순서다.- 인접 리스트를 오름차순 정렬했기 때문에 “작은 번호부터 깊게” 들어간다.
- DFS의 되돌아옴(backtracking)은 재귀 호출이 끝나면서 자연스럽게 발생한다.
BFS 방문 순서 실습: A01Bfs방문순서
이 코드는 BFS의 방문 순서를 출력하면서, visited 처리를 어디서 해야 하는지를 포인트로 잡고 있다.
BFS 기본 구조
Queue<Integer> myQue = new LinkedList<>();
myQue.add(0);
visited[0] = true;
while (!myQue.isEmpty()) {
int temp = myQue.poll();
System.out.println(temp);
for (int a : adjList.get(temp)) {
if (!visited[a]) {
myQue.add(a);
visited[a] = true;
}
}
}visited는 “큐에 넣을 때” 처리해야 하는 이유
BFS에서 visited를 poll 시점에 처리하면, 같은 노드가 여러 부모를 통해 중복으로 큐에 들어갈 수 있어 큐가 불필요하게 커질 수 있다.
그래서 일반적으로 enqueue(큐에 add) 시점에 visited=true로 확정해 중복 삽입을 차단한다.
BFS 최단거리 실습: A02Bfs최단거리
이 코드는 “0에서 target까지의 최단거리”를 BFS로 구한다.
상태를 큐에 같이 들고 다니기
여기서는 Queue<int[]>를 써서 {노드번호, 거리}를 함께 저장한다.[4]
myQue.add(new int[]{0, 0}); // {node, dist}
visited[0] = true;즉, BFS 레벨 탐색을 하면서 “이 노드에 도달했을 때의 거리”를 같이 전파하는 방식이다
종료 방식 2가지(코드에 있는 TODO)
방법(1): poll해서 꺼낸 뒤 목표인지 확인
int[] temp = myQue.poll();
if (temp[0] == target) {
answer = temp[1];
break;
}- 구현이 직관적이다
- 하지만 target이 이미 큐에 들어가 있어도 “꺼낼 때까지”는 계속 루프가 돈다
방법(2): 큐에 넣는 순간 목표면 바로 종료
myQue.add(new int[]{a, temp[1] + 1});
visited[a] = true;
if (target == a) {
answer = temp[1] + 1;
break loop1;
}- target을 발견한 즉시 종료할 수 있어 더 빠를 수 있다.
- 입력이 커지면 “꺼내기 전 종료”가 시간 측면에서 유리해질 여지가 있다.
다른 방식: 거리 배열(distance[])
또 다른 방식은 distance[] 배열을 두고 distance[next] = distance[cur] + 1로 기록하면서 BFS를 진행하는 방법이다
이 방식은 {노드, 거리}를 큐에 넣지 않아도 되고, 거리 관리가 깔끔해지는 장점이 있다.
그외 BFS 유형 정리: A04그외유형
1) 2차원 배열의 최단거리
2차원 격자에서 최단거리는 보통 BFS로 풀고, 큐에 (x, y, dist) 같은 상태를 넣어 상하좌우로 확장한다.
이때도 dx/dy로 방향을 통일하고, visited[][] 또는 dist[][]로 재방문을 막아야 최단거리가 보장된다.
2) 비노드 형식 거리 문제: 숨바꼭질(1697)
숨바꼭질(1697)은 그래프가 명시적으로 주어지지 않고 “현재 위치 x에서 x-1, x+1, 2x로 이동” 같은 규칙으로 다음 상태가 만들어지는 유형이다.
여기서도 본질은 BFS 최단거리이고, 중복 상태를 막기 위한 방문 체크는 boolean[] visited로 충분하지만 Set으로도 구현할 수 있다(범위가 고정이면 배열이 더 일반적).
활용