문제
시간 제한 2초
그래프를 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
문제 풀이
사실 이미 문제 제목에서부터 DFS 와 BFS 를 구하는 문제이기 때문에 이 두가지 알고리즘을 안다면 쉽게 풀 수 있을것 같다.
N 은 노드의 개수, M 은 에지의 개수, V 는 시작 노드이며
M 개의 줄에 두 개의 노드를 각 각 입력 받는 상태이다.
예제 입력1 에서 N = 4, M = 5, V = 1 로 입력받은 상태이고
노드를 입력받았다고 가정하면 인접 리스트는 다음과 같다.
여기서 문제에 나와있는 단, 방문할 수 있는 노드가 여러 개인 경우에는 노드 번호가 작은 것을 먼저 방문 하라는 내용이 있기 때문에 인접리스트를 정렬을 시켜줘야 한다.
이렇게 정렬을 시켜주고 각 각의 노드를 방문하였는지 체크해주는 배열 (여기서는 visited라는 배열) 을 이용한다.
DFS
-
처음 시작점인 1부터 방문하여 방문배열에 1을 true로 바꿔주고 인접 노드인 2, 3, 4 중 2를 재귀함수로 호출한다.
-
방문배열에 2를 true로 바꿔주고 2 의 인접 노드인 1, 4 중 1은 이미 방문하였기 때문에 제외하고 4를 재귀함수로 호출한다.
- 방문배열에 4를 true 로 바꿔주고 4의 인접 노드인 1, 2, 3 중 1, 2는 이미 방문하였기 때문에 제외하고 3을 재귀함수로 호출한다.
- 방문배열에 3을 true 로 바꿔주고 3의 인접 노드인 1, 4 는 이미 방문하였었기 때문에 함수 로직을 끝내고 출력하면 1 - 2 - 4 - 3 순으로 나오게 된다.
BFS
breath-first-search (너비 우선 탐색)는 그래프를 완전 탐색하는 방법이며 시작 노드에서부터 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하는 탐색 알고리즘 이라고 한다.
FIFO : 선입 선출 방식인 큐를 이용하여 구현한다.
BFS 에는 큐가 필요하기 때문에 큐를 먼저 생성한다.
- 처음 시작점인 1부터 방문하여 방문배열에 1을 true로 바꿔주고 여기서 큐에는 1을 넣어준다.
- 큐에서 1을 꺼내면서 인접 노드에 2, 3, 4 를 큐에 삽입한다. 이때 큐에 들어가는 노드들은 어차피 모두 한번씩 방문하여야 하기 때문에 방문 배열에 2, 3, 4를 모두 true 로 바꿔준다.
- 그리고 큐에 있는 노드들이 비어있을 때까지 계속 반복하여서 출력하면 1 - 2 - 3 - 4 순으로 출력된다.
이를 코드에 적용하면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class DFS와BFS {
private static ArrayList<Integer>[] A;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
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()); // 시작 노드 번호
A = new ArrayList[N + 1]; // A 는 인접 리스트로 N + 1로 한 이유는 인덱스 번호를 1부터 시작하기 위해서
visited = new boolean[N + 1]; // 방문 배열을 체크해주는 배열
for(int i = 1; i <= N; i++) {
A[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
A[start].add(end); // 인접 리스트에 start 번째에는 end 를 end 번째에는 start 를
A[end].add(start); // 양쪽에 넣어준다.
}
for(int i = 1; i <= N; i++) {
Collections.sort(A[i]);
}
DFS(V);
visited = new boolean[N + 1];
sb.append("\n");
BFS(V);
System.out.println(sb);
}
private static void DFS(int V) {
if(!visited[V]) { // 방문했던 노드인지 체크하는 조건문
sb.append(V + " "); // 방문한 노드를 StringBuilder 에 저장
visited[V] = true; // 방문한 노드는 체크
for(int i : A[V]) { // 인접한 노드를 for 문으로 확인
if(!visited[i]) { // 방문하지 않았던 노드이면 DFS 재귀함수로 호출
DFS(i);
}
}
}
}
private static void BFS(int V) {
Queue<Integer> queue = new LinkedList<>(); // BFS 알고리즘을 사용하기 위한 큐 생성
queue.add(V); // 탐색할 노드를 큐에 삽입 후 방문 배열을 true 로 바꿔줌
visited[V] = true;
while(!queue.isEmpty()) { // 큐가 비어있을 떄까지 while 문으로 반복
int now = queue.poll(); // 큐에 있는 값을 poll 하고 StringBuilder 에 추가
sb.append(now + " ");
for(int i : A[now]) { // poll 한 값에 인접 노드를 살펴 보면서 큐에 삽입하고 방문 배열을
if(!visited[i]) { // true 로 바꿔줌
queue.add(i);
visited[i] = true;
}
}
}
}
}회고
DFS 와 BFS 알고리즘을 잘 이해했는지 테스트하는 문제였던 것 같다. DFS 는 공부해서 구현은 할 수 있었지만 BFS 는 막상 구현하려다보니 어려웠었다. 아직 문제이 익숙치 않은 것 같아서 계속 문제를 풀어보면서 실력을 다져보겠다!!
