[백준] 1260번 DFS와 BFS 문제풀이 (JAVA)
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4예제 출력 1
1 2 4 3
1 2 3 4예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1예제 출력 2
3 1 2 5 4
3 1 4 2 5
DFS와 BFS
문제의 질문 자체는 단순하다.
제목 그대로 DFS와 BFS를 이용해서 답을 구하면 되는 문제이다.
그래프는 기본적으로 Cyclic 구조이며, 예제입력 1번을 그림으로 표시하면 다음과 같다.
DFS와 BFS가 어떤 방식인지 모르시는 분들을 위해 짧게 설명하자면,
DFS는 깊이우선탐색 방법으로, 말그대로 한쪽 노드의 가장 깊은곳까지 탐색한 후 다른 노드의 가장깊은곳을 차례로 탐색하는 방식이다.
위 그림에서 예제입력 1번대로 행한다면, 1번노드로 진입해서 자식노드 중 가장 작은 2번을 거쳐 가장 깊은 4번까지 탐색할것이다. 이후 1번에서 또다른 자식노드 3을 탐색한다.
DFS의 그런 특징을 이용하여 2차원배열에 각 노드크기에 해당하는 index에 담고 재귀함수를 호출할것이다.
BFS는 너비우선탐색 방법이다. 레벨별로 차례차례 탐색하는 방식으로, 위 그림에서는 1 -> 2 -> 3 -> 4 순서가 되겠다.
BFS는 각 레벨별로 차례대로 queue에 담고 하나씩 꺼내올것이다.
그럼, 바로 코드를 보며 설명하겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Solution {
static int[][] arr; // 재귀함수를 돌면서 매번 초기화되면 안되기 때문에 static으로 선언!
static boolean[] visited; // 특정 노드의 출력 여부를 표시
static Queue<Integer> queue = new LinkedList<>(); // BFS에서 사용할 큐
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()); // 띄어쓰기 단위로 입력받은 3개의 숫자를 각각에 할당
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
arr = new int[N+1][N+1]; // 노드1은 1행, 노드4는 4행에 담을것이므로 0행0열은 비워둔다.
for (int i = 0; i < M; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st2.nextToken());
int y = Integer.parseInt(st2.nextToken());
arr[x][y] = 1; // 양방향 간선으로 연결된 두 정점 표시
arr[y][x] = 1; // ex) arr[1][2]는 1과2로 연결된 간선이다.
}
visited = new boolean[N + 1];
DFS(V);
System.out.println();
visited = new boolean[N + 1];
BFS(V);
}
}
가장 먼저, 데이터를 입력받는 부분이다.
백준 문제풀이에서는 기본적으로 변수를 단순하게 제공하지 않는다.
Scanner 혹은 BufferedReader를 통해 데이터를 입력받아 풀도록 되어있다.
보통 자바를 배우는 단계에서 쉽고 빠르게 작성이 가능한 Scanner를 먼저 배우고 이것에 익숙하신 분들도 계실것이다.
물론 장단점이 있지만 코딩테스트의 효율성에서 가장 큰 비중을 차지하는 속도 측면에서 BufferedReader가 더 빠르다.
코테에서는 왠만해서는 BufferedReader를 사용하자.
위 코드에서는 그렇게 입력받은 데이터를 StringTokenize를 이용해 띄어쓰기 간격으로 데이터를 나눠서 객체로 잡았다.
이 외에 코드 설명은 주석을 보도록 하자.
다음으로 DFS 함수를 보자.
public static void DFS(int V) {
System.out.print(V + " "); // 먼저 들어오는 노드부터 출력
visited[V] = true; // 출력한 노드는 다시 재귀호출하면 안되므로 true 처리
for (int i = 1; i < arr[V].length; i++) {
if (arr[V][i] == 1 && !visited[i]) { // 두 수 사이에 간선이 있고 방문하지 않았으면 재귀호출
DFS(i);
}
}
}예제 1번으로 예를들면, 맨 처음 V = 1이 들어오면서 1이 출력될것이다.
다음으로 i는 1부터 for문을 도는데, arr[][]에서 0행0열은 모두 0으로 표시했기 때문에
각 노드 크기에 맞는 index = 1부터 간선유무를 체크하면된다.
또한, 각 노드 크기에 따라 arr에서 index를 차지했기 때문에 for문을 돌면서 방문하는 재귀호출은 자연스럽게 오름차순이 된다.
다음은 BFS를 보자.
public static void BFS(int V) {
System.out.print(V + " ");
visited[V] = true;
for (int i = 1; i < arr[V].length; i++) {
if (arr[V][i] == 1 && !visited[i]) {
queue.offer(i); // 간선이 있고 방문하지 않았으면 오름차순으로 queue에 넣는다.
visited[i] = true; // 넣자마자 true로 바꿔준다.
}
}
while (!queue.isEmpty()) { // 먼저 들어간 순서대로 빼면서 재귀호출을 돌며 출력해준다.
BFS(queue.poll());
}
}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;
class Solution {
static int[][] arr;
static boolean[] visited;
static Queue<Integer> queue = new LinkedList<>();
public static void DFS(int V) {
System.out.print(V + " ");
visited[V] = true;
for (int i = 1; i < arr[V].length; i++) {
if (arr[V][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
public static void BFS(int V) {
System.out.print(V + " ");
visited[V] = true;
for (int i = 1; i < arr[V].length; i++) {
if (arr[V][i] == 1 && !visited[i]) {
queue.offer(i);
visited[i] = true;
}
}
while (!queue.isEmpty()) {
BFS(queue.poll());
}
}
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());
arr = new int[N+1][N+1];
for (int i = 0; i < M; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st2.nextToken());
int y = Integer.parseInt(st2.nextToken());
arr[x][y] = 1;
arr[y][x] = 1; // 양방향 간선으로 연결된 두 정점 표시
}
visited = new boolean[N + 1];
DFS(V);
System.out.println();
visited = new boolean[N + 1];
BFS(V);
}
}BufferedReader 및 StringTokenizer로 데이터를 입력받는 방식,
DFS 기본방식,
BFS 기본방식 등 기본기를 다지기에 좋은 문제다.
풀이방법도 다양하니, 이 글 말고도 다른 풀이방법도 참고해서 시야를 넓히면 좋을 것이다.