최단 경로 탐색 방법에는 여러가지가 있다. 그 중 dfs (깊이 우선 탐색), bfs (너비 우선 탐색), dijkstra(다익스트라) 방식을 java를 활용해 코드로 작성해 볼려고 한다.
먼저 데이터를 파일로부터 읽어 올 수 있도록 파일 데이터를 작성해주었다.
dfs와 bfs를 할때의 그래프는 가중치(weight)가 존재하지 않고 각각의 그래프가 연결되어 있는 형태로만 존재한다.
다음은 그래프를 파일 데이터 형태로 만들어 준 것이다. 그래프의 총 길이는 8이기 때문에 최 상단부에는 8이라는 데이터가 들어간다. 이후 1번 노드와 연결 되어 있는 값, 2번 노드, 3번 노드... 이렇게 총 8번 노드가 이어져있는 모습까지 구현해 주었다.
다음으로는 이 파일을 코드로 읽어 와서 인접 행렬(adjmatrix)에 저장해 주는 코드를 소개하겠다.
private static void makeList(String filename) {
try (Scanner file = new Scanner(new File(filename))) {
int count = 1;
while (file.hasNextLine()) {
System.out.println("그래프 [" + count + "]");
String graphlength = file.nextLine();
Integer matrixlen = Integer.parseInt(graphlength);
int[][] adjmatrix = new int[matrixlen][matrixlen];
for (int i = 0; i < matrixlen; i++) {
String datafield = file.nextLine();
String[] stringdata = datafield.split(" ");
int[] data = new int[stringdata.length];
for (int j = 0; j < stringdata.length; j++) {
data[j] = Integer.parseInt(stringdata[j]);
}
int coldata = data[0] - 1;
int[] rowdata = new int[data.length - 1];
for (int j = 1; j < data.length; j++) {
rowdata[j - 1] = data[j] - 1;
}
for (int j = 0; j < rowdata.length; j++) {
adjmatrix[coldata][rowdata[j]] = 1;
}
}
System.out.println("인접 행렬 구현");
for(int i = 0; i < matrixlen; i++) {
for(int j = 0; j < matrixlen; j++) {
System.out.print(adjmatrix[i][j] + " ");
}
System.out.println();
}
System.out.println("-".repeat(33));
System.out.println("깊이 우선 탐색");
dfs(adjmatrix);
System.out.println();
System.out.println("너비 우선 탐색");
bfs(adjmatrix);
System.out.println("=".repeat(33));
count++;
}
} catch (FileNotFoundException e) {
System.out.println("파일 이름을 확인하세요.");
}
}
파일을 하나씩 읽어와 인접행렬에 저장해주는 코드로 결과는 다음과 같다.
이 인접 행렬을 이용하여 dfs와 bfs를 구현해 보았다.
dfs(깊이 우선 탐색) 코드
private static void dfs(int[][] matrix) {
Stack<Integer> stack = new Stack<>();
List<Integer> visited = new ArrayList<>();
stack.push(0);
int length = matrix[1].length;
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited.contains(v)) {
for (int i = length - 1; i >= 0; i--) {
if (matrix[v][i] == 1 && v != i) {
stack.push(i);
}
}
visited.add(v);
System.out.print((v + 1) + " ");
}
}
}
bfs(너비 우선 탐색) 코드
private static void bfs(int[][] matrix) {
Queue<Integer> q = new LinkedList<>();
List<Integer> visited = new ArrayList<>();
q.offer(0);
int l = matrix[1].length;
while (!q.isEmpty()) {
int v = q.poll();
if (!visited.contains(v)) {
for (int i = 0; i < l; i++) {
if (matrix[v][i] == 1 && v != i) {
q.offer(i);
}
}
visited.add(v);
System.out.print((v + 1) + " ");
}
}
System.out.println();
}
dfs와 bfs 실행시 나오는 결과 값
이렇게 dfs와 bfs를 코드로 구현할 수 있었고 실행결과도 원래 답과 일치 한다는 것도 파악할 수 있었다. 다음글에서는 dijkstra 알고리즘의 코드를 설명하도록 하겠다.