최단거리 계산 을 위해서 DFS, BFS 탐색 알고리즘이 사용된다.
breadth first search (BFS) and depth first search (DFS).
위 두 알고리즘의 소스는 다음과 같다.
DFS (재귀호출 사용), BFS(Queue 사용)
입력값
4 5 1 1 2 1 3 1 4 2 4 3 4 |
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main {
private static int[][] map; private static boolean[] visited; private static int maxLength;
public static void main(String[] args) {
try { System.setIn(new FileInputStream("res/sample_input.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); }
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); int M = sc.nextInt(); int V = sc.nextInt();
int start = 0; int end = 0;
map = new int[N+1][N+1]; maxLength = map.length; visited = new boolean[maxLength];
for (int i = 1; i < N+1; i++) { for (int j = 1; j < N+1; j++) { map[i][j] = 0; } }
for (int i = 0; i < M; i++) { start = sc.nextInt(); end = sc.nextInt();
map[start][end]=1; map[end][start]=1; }
initVisited(); dfs(V); System.out.println(); initVisited(); bfs(V); }
private static void initVisited() { for (int i = 0; i < maxLength; i++) { visited[i] = false; } }
private static void dfs(int v ){ visited[v] = true; System.out.print(v + " "); for (int i = 0; i < maxLength; i++) { if((map[v][i] == 1 ) && !visited[i]) { dfs(i); } } }
private static void bfs(int v) { visited[v] = true; System.out.print(v + " "); Queue q = new LinkedList();
q.add(v); while (q.size() > 0 ) { v = (int)q.peek(); for (int i = 1; i < maxLength; i++) { if((map[v][i] == 1) && !visited[i]) { q.add(i); visited[i] = true; System.out.print(i + " "); } q.remove(v); } } } } |
결과
1 2 4 3 1 2 3 4 |