문제
N개의 노드와 M개의 간선으로 이루어진 무방향 그래프를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다. 방문할 수 있는 노드가 여러 개인 경우 번호가 작은 것부터 방문하며, 시작 노드 V가 주어진다.
입력
- 첫 번째 줄: 노드 수 N (1 이상 1,000 이하), 간선 수 M (1 이상 10,000 이하), 시작 노드 V
- 이후 M줄: 연결된 두 노드 번호
출력
첫 번째 줄에 DFS 탐색 결과, 두 번째 줄에 BFS 탐색 결과를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 5 1 1 2 1 3 1 4 2 4 3 4 | 1 2 4 3 1 2 3 4 |
풀이
인접 리스트를 정렬하여 작은 번호 노드부터 탐색하도록 준비한 후, DFS와 BFS를 각각 구현하여 결과를 출력한다.
- 각 노드의 인접 리스트를
List<Integer>[]로 구성하고 양방향으로 추가한다. - 모든 인접 리스트를 정렬(
Collections.sort)하여 작은 번호 우선 탐색을 보장한다. - DFS: 재귀로 현재 노드를 방문 처리하고 인접 노드를 순서대로 재귀 호출한다.
- BFS: 큐를 활용하여 시작 노드부터 레벨 순으로 방문하며, 큐에 넣을 때 방문 처리한다.
- DFS 이후
visited배열을 초기화하여 BFS에서 재사용한다.
핵심 아이디어: 인접 리스트를 사전에 정렬함으로써 DFS와 BFS 모두 번호 순으로 탐색하는 조건을 만족시킨다. BFS에서는 노드를 큐에 추가할 때 방문 처리해야 중복 삽입을 방지할 수 있다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day55BOJ1260DFS와BFS정석으로구현해보기 {
static int N, M, V;
static StringBuilder sb;
static List<Integer>[] list; // 하위 노드 갯수가 불명이므로, List<숫자>로 배열생성
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1]; // 인덱스를 그대로 사용하기 위해 +1
visited = new boolean[N + 1];
for (int i = 1; i < N + 1; i++) {
list[i] = new ArrayList<>();
} // 인덱스에 맞게 List에 객체 생성
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
list[n1].add(n2);
list[n2].add(n1); // 양방향이 가능하므로 서로 원소에 추가
}
for (int i = 1; i < N + 1; i++) {
Collections.sort(list[i]);
} // 경로가 많을 때 작은 수부터
dfs(V);
sb.append("\n");
visited = new boolean[N + 1]; // dfs때 사용한 boolean초기화
bfs(V);
System.out.println(sb);
br.close();
}
private static void dfs(int v) {
if (visited[v])
return; // for문에서 아예 안들어오도록 조건문 가능.
visited[v] = true; // v를 방문했고,
sb.append(v).append(" "); // 그 값을 출력
for (int i : list[v]) { // v의 작은 수 부터 노드에 재귀
dfs(i);
}
}
private static void bfs(int v) {
Queue<Integer> q = new LinkedList<>();
q.offer(v); // 처음값 큐에 넣고,
visited[v] = true; // 방문처리
while (!q.isEmpty()) { // 큐가 빌때까지 실행
int n = q.poll(); // 현재 큐에서 값을 꺼내서
sb.append(n).append(" "); // 방문했으니 출력
for (int i : list[n]) { // 노드를 하나씩 부르고
if (!visited[i]) { // 방문하지 않는 노드들을 모두 큐에 넣음
q.offer(i);
visited[i] = true; // 큐에 들어간 노드는 다시 큐에 넣지 않도록 방문처리
}
}
}
}
}복잡도
- 시간: O(V + E) — DFS와 BFS 각각 모든 노드와 간선을 한 번씩 방문 (정렬 O(E log E) 포함)
- 공간: O(V + E) — 인접 리스트, visited 배열, BFS 큐