BOJ 1260
위 문제는 백준 사이트의 알고리즘 1260 문제에 관한 설명입니다.
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
private static int[][] map;
private static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
int v = Integer.parseInt(temp[2]);
map = new int[n+1][n+1];
visit = new boolean[n+1];
while(0 < m)
{
temp = br.readLine().split(" ");
int x = Integer.parseInt(temp[0]);
int y = Integer.parseInt(temp[1]);
map[x][y] = map[y][x] = 1;
m--;
}
dfs(v, n);
System.out.println("");
visit = new boolean[n+1];
bfs(v, n);
}
private static void bfs(int k, int n){
Queue<Integer> queue = new <Integer>LinkedList();
queue.offer(k);
while(!queue.isEmpty()){
int temp = queue.poll();
visit[temp] = true;
System.out.print(temp + " ");
for (int i = 1; i<=n;i++)
{
if(map[temp][i] ==1 && !visit[i]){
queue.offer(i);
visit[i] = true;
}
}
}
}
private static void dfs(int k, int n ) {
if (visit[k])
return;
visit[k]= true;
System.out.print(k+" ");
for(int i=1;i<=n;i++)
{
if(map[k][i]==1)
dfs(i,n);
}
}
}
temp 배열에 정점, 간선, 시작번호를 받습니다.
split을 사용해서 값이 배열로 구분되기때문에 n m v로 각 값들을 옮겨주고
어디에 옮겨졌는지 확인할 M과 visit으로 방문했는지를 체크합니다.
이후에 간선이 어떻게 되어있는지를 입력해주어야하기에
아까 만들었던 temp를 활용해서 값을 받고 x와 y에 값을넣습니다.
이때 map x y 와 y x에 1를 넣는 이유는 1, 2간선과 2, 1간선은 연결되어있기 때문입니다.
그리고 간선의 갯수 m을 줄여주면서 반복합니다.
이후 dfs를 하게 되는데 시작점 k와 정점 n을 넘겨받아와 재귀함수를 응용하여 풀어냅니다.
만약 K점이 방문되어있는상태라면 return을 하고 방문안된 상태라면 visit을 true로
그리고 현재 진행중인곳의 위치K를 확인해서 출력합니다.
이후 for문을 이용해서 간선이라면 dfs를 다시 반복시킵니다.
재귀함수를 이용했기때문에 순차적으로 진행이 되게되고 다돌았을때 dfs부분은 끝이납니다.
그리고 한번 방문했기 때문에 visit에는 값들이 남겨져있습니다.
따라서 new로 새로 만들어줍니다. bfs를 이제는 시작하는데 bfs는 큐를 사용해서 푸는게 좋습니다.
시작점 K를 넣어주고, temp에 방문한 지점K를 넣어줍니다.
나머지 과정은 dfs과 동일합니다.
stack을 이용했느냐 queue를 이용했느냐의 차이지 알고리즘적으로는 유사하기 때문입니다.