문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1<=N<=1000), 간선의 개수 M(1<=M<=10000), 탐색을 시작할 정점의 번호 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
예제 입력 3
1000 1 1000
999 1000
예제 출력 3
1000 999
1000 999
풀이
- 입력으로 주어진 간선의 정보를 저장히기 위해 인접행렬을 사용한다.
- 정점의 값을 그대로 배열의 index로 사용하기 위해 범위보다 1 큰 크기의 2차원 배열을 선언하고, 입력 받은 간선 정보에 해당하는 배열 값을 1로 한다.(가중치가 없는 그래프이기 때문에 인접해 있는 지 아닌 지만 판단하기 위해 1 사용)
- DFS 수행
- BFS 수행
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int n, m, V;
static int[][] nums;
static boolean[] visited;
static StringBuilder sb = null;
static Queue<Integer> q;
public static void main(String[] args) throws IOException, NumberFormatException{
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());
// 정점 값을 그대로 배열의 인덱스로 사용하기 위해
// N의 범위보다 1 더 큰 크기로 선언
nums = new int[1001][1001];
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
// 양방향 간선이므로 양쪽 다 1로 만들기
// 가중치 없는 그래프이므로 1
// 1이면 인접, 0이면 인접 ㄴㄴ
nums[from][to] = nums[to][from] = 1;
}
visited = new boolean[1001];
sb = new StringBuilder();
dfs(V);
System.out.println(sb);
visited = new boolean[1001];
sb = new StringBuilder();
bfs(V);
System.out.println(sb);
}
static void dfs(int index) {
// 시작 정점
visited[index] = true;
sb.append(index + " ");
// 끝까지 탐색 다 하면 return
if(index == n+1) return;
for(int i=1; i<n+1; i++) {
// 인접해있고, 탐색하지 않은 경우
if(nums[index][i] == 1&&!visited[i])
dfs(i);
}
}
static void bfs(int index) {
q = new ArrayDeque<>();
// 시작 정점
q.add(index);
visited[index] = true;
sb.append(index + " ");
while(!q.isEmpty()) {
int now = q.poll();
for(int i=1; i<n+1; i++) {
// 인접해있고, 탐색하지 않은 경우
if(nums[now][i] == 1&&!visited[i]) {
q.add(i);
visited[i]= true;
sb.append(i + " ");
}
}
}
}
}