문제 요약
정점 개수 n, 간선 개수 m, 시작 정점 v가 주어질 때,
- DFS로 방문한 순서
- BFS로 방문한 순서
를 각각 한 줄씩 출력하는 문제다.
단, 방문할 수 있는 정점이 여러 개면 번호가 작은 정점부터 방문해야 한다.
핵심 아이디어(왜 인접 리스트 + 정렬인가?)
그래프 입력은 간선 목록으로 들어오지만, 탐색(DFS/BFS)은 “현재 정점에서 갈 수 있는 인접 정점 목록”이 필요하므로 인접 리스트로 변환한다.
또한 이 문제는 “가능한 다음 정점이 여러 개면 작은 번호부터” 규칙이 있어, 각 정점의 인접 리스트를 오름차순 정렬해두면 DFS/BFS에서 단순히 for-each로 순회하는 것만으로 요구 방문 순서를 만족한다.
입력 처리 & 인접 리스트 구성
코드 흐름은 다음과 같다.
n, m, v입력adjList를n+1크기로 생성 (정점 번호가 1부터라 0은 더미)- 간선
m개 입력받아 양방향으로 추가 - 각 정점의 인접 리스트 오름차순 정렬
adjList = new ArrayList<>();
for (int i = 0; i < n + 1; i++) adjList.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int nodeA = ...
int nodeB = ...
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}이렇게 해두면 “작은 번호 우선 방문” 규칙을 DFS/BFS 로직에서 별도로 처리할 필요가 없다.
DFS 구현(재귀)
DFS는 “현재 노드 방문 → 인접 노드 중 미방문이면 재귀로 더 깊게” 구조다.
static void dfs(int start) {
dfsSb.append(start).append(" ");
visited[start] = true;
for (int target : adjList.get(start)) {
if (!visited[target]) {
dfs(target);
}
}
}포인트:
- 방문 즉시
visited[start] = true - 인접 리스트가 오름차순 정렬돼 있으므로 작은 정점부터 깊게 들어간다.
StringBuilder로 방문 순서를 누적해 출력 형식을 맞춘다(공백 포함).
BFS 구현(큐)
BFS는 “큐에 넣고 → 하나 꺼내서 방문 처리/출력 → 그 노드의 인접 미방문 노드를 큐에 넣기”를 반복한다.
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int target = queue.poll();
bfsSb.append(target).append(" ");
for (int a : adjList.get(target)) {
if (!visited[a]) {
visited[a] = true;
queue.add(a);
}
}
}
}포인트:
- visited는 큐에 넣는 시점에 true 처리해야 같은 노드가 중복으로 큐에 들어가는 것을 막는다.
- DFS와 동일하게 인접 리스트가 정렬되어 있어 “작은 번호 우선”이 유지된다.
visited 초기화가 필요한 이유
DFS를 한 번 돌고 나면 visited가 true로 채워져 있다.
BFS는 DFS와 독립적으로 “처음부터 다시 탐색”해야 하므로, DFS 이후에 visited를 새로 만들어 초기화한다.
visited = new boolean[n + 1];
dfs(v);
visited = new boolean[n + 1];
bfs(v);이게 없으면 BFS는 이미 방문 처리된 상태로 시작해서 제대로 탐색하지 못한다.
전체 코드(제출용)
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// DFS와 BFS
public class S1260_class {
static int n;
static int m;
static int v;
static List<List<Integer>> adjList;
static boolean[] visited;
static StringBuilder dfsSb = new StringBuilder();
static StringBuilder bfsSb = new StringBuilder();
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());
m = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
adjList = new ArrayList<>();
for (int i = 0; i < n + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
StringTokenizer input = new StringTokenizer(br.readLine());
int nodeA = Integer.parseInt(input.nextToken());
int nodeB = Integer.parseInt(input.nextToken());
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}
visited = new boolean[n + 1];
dfs(v);
System.out.println(dfsSb);
visited = new boolean[n + 1];
bfs(v);
System.out.println(bfsSb);
}
static void dfs(int start) {
dfsSb.append(start).append(" ");
visited[start] = true;
for (int target : adjList.get(start)) {
if (!visited[target]) {
dfs(target);
}
}
}
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int target = queue.poll();
bfsSb.append(target).append(" ");
for (int a : adjList.get(target)) {
if (!visited[a]) {
visited[a] = true;
queue.add(a);
}
}
}
}
}
Eazy하게