DFS 깊이 우선 탐색 Stack & Queue

1. Stack_ver

package week_4;
 
import java.util.Arrays;
import java.util.Stack;
 
public class DFS_LabyrinthSearch {
    public static void main(String[] args) {
        int cnt = 0;
        int[][] load = { { 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0 },
                { 0, -1, -1, -1, 0, -1, -1, 0, -1, -1, -1, -1, 0, 0, 0, -1, },
                { 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, 0, 0, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, -1, -1, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0 },
                { 0, -1, 0, -1, 0, -1, -1, 0, -1, 0, -1, -1, 0, -1, -1, 0 },
                { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 0 },
                { 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0 },
                { 0, -1, 0, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
                { 0, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, -1, 0, 0, 0, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, 0 },
                { 0, -1, 0, -1, -1, -1, -1, 0, 0, 0, 0, -1, -1, -1, 0, 0 },
                { -1, -1, 0, -1, -1, -1, -1, 0, -1, -1, 0, 0, -1, 0, -1, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 0, -1, 0, -1, -1 },
                { 0, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0 } };
        int x = 0; // x좌표
        int y = 0; // y좌표
        int[] end = { 15, 15 }; // 종료 위치
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] { 0, 0 });// 우좌상하
 
        do {
 
            int[] ps = stack.pop();
            x = ps[1];// x좌표 0
            y = ps[0];// y좌표 15
 
            if (end[0] == y && end[1] == x) {
                System.out.println("정답 : " + y + " , " + x);
                load[y][x] = -2;
                break;
            }
            load[y][x] = -2;// 지나간 좌표
            if (x > 0) {
                if (load[y][x - 1] >= 0) {// 왼쪽 타일값이 0일경우 =>>왼쪽 타일 검색
                    load[y][x - 1] = 2;
                    stack.push(new int[] { y, x - 1 });
 
                }
            }
            if (x < load[y].length - 1) {// 현재위치의 x좌표가 x축 끝 좌표보다 작고
                if (load[y][x + 1] >= 0) {// 오른쪽의 타일값이 0보다 클 경우 =>>오른쪽 타일 검색 || 타일의값이 0이면 아직 안간 곳 || 조건을 크거나 같다 한 이유는
                                            // 목표값이 100이기떄문이다
                    load[y][x + 1] = 2;
                    stack.push(new int[] { y, x + 1 });
                }
            }
 
            if (y > 0) {
                if (load[y - 1][x] >= 0) {// 위쪽 타일검색
                    load[y - 1][x] = 2;
                    stack.push(new int[] { y - 1, x });
                }
            }
            if (y < load.length - 1) {
                if (load[y + 1][x] >= 0) {// 아래쪽 타일검색
                    load[y + 1][x] = 2;
                    stack.push(new int[] { y + 1, x });
                }
 
            }
 
            if (stack.isEmpty()) { // 길을 다 돌때 까지 종료를 못찾은 경우
                break;
            }
 
        } while (true);
 
        for (int i = 0; i < load.length; i++) {
            for (int j = 0; j < load[i].length; j++) {
                if (load[i][j] == 0) {
                    System.out.print("□");
                } else if (load[i][j] == -2) {
                    if (i == 15 && j == 15) {
                        System.out.print("X");
                    } else {
                        System.out.print("@");
                    }
                } else if (load[i][j] == -1) {
                    System.out.print("■");
                } else if (load[i][j] == 2) {
                    System.out.print("$");
                }
            }
            System.out.println();
        }
        while (!stack.isEmpty()) {
            System.out.println(Arrays.toString(stack.pop()));
        }
    }
}
 

2. Queue_ver

package week_4;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class DFS_LabyrinthSearch {
    public static void main(String[] args) {
        int[][] load = { { 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0 },
                { 0, -1, -1, -1, 0, -1, -1, 0, -1, -1, -1, -1, 0, 0, 0, -1, },
                { 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, 0, 0, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, -1, -1, -1, -1, 0, -1, 0, -1, -1, -1, -1, 0, -1 },
                { 0, -1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0 },
                { 0, -1, 0, -1, 0, -1, -1, 0, -1, 0, -1, -1, 0, -1, -1, 0 },
                { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 0 },
                { 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0 },
                { 0, -1, 0, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
                { 0, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, -1, 0, 0, 0, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, 0 },
                { 0, -1, 0, -1, -1, -1, -1, 0, 0, 0, 0, -1, -1, -1, 0, 0 },
                { -1, -1, 0, -1, -1, -1, -1, 0, -1, -1, 0, 0, -1, 0, -1, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 0, -1, 0, -1, -1 },
                { 0, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0 } };
        int x = 0; // x좌표
        int y = 0; // y좌표
        int[] end = { 15, 15 }; // 종료 위치
 
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { 0, 0 });// 우좌상하
 
        do {
            int[] ps = changeQueue(queue);
            x = ps[1];// x좌표 0
            y = ps[0];// y좌표 15
 
            if (end[0] == y && end[1] == x) {
                System.out.println("정답 : " + y + " , " + x);
                load[y][x] = -2;
                break;
            }
            load[y][x] = -2;// 지나간 좌표
            if (x > 0) {
                if (load[y][x - 1] >= 0) {// 왼쪽 타일값이 0일경우 =>>왼쪽 타일 검색
                    load[y][x - 1] = 2;
                    queue.offer(new int[] { y, x - 1 });
 
                }
            }
            if (x < load[y].length - 1) {// 현재위치의 x좌표가 x축 끝 좌표보다 작고
                if (load[y][x + 1] >= 0) {// 오른쪽의 타일값이 0보다 클 경우 =>>오른쪽 타일 검색 || 타일의값이 0이면 아직 안간 곳 || 조건을 크거나 같다 한 이유는
                                            // 목표값이 100이기떄문이다
                    load[y][x + 1] = 2;
                    queue.offer(new int[] { y, x + 1 });
                }
            }
 
            if (y > 0) {
                if (load[y - 1][x] >= 0) {// 위쪽 타일검색
                    load[y - 1][x] = 2;
                    queue.offer(new int[] { y - 1, x });
                }
            }
            if (y < load.length - 1) {
                if (load[y + 1][x] >= 0) {// 아래쪽 타일검색
                    load[y + 1][x] = 2;
                    queue.offer(new int[] { y + 1, x });
                }
 
            }
 
            if (queue.isEmpty()) { // 길을 다 돌때 까지 종료를 못찾은 경우
                break;
            }
 
        } while (true);
 
        for (int i = 0; i < load.length; i++) {
            for (int j = 0; j < load[i].length; j++) {
                if (load[i][j] == 0) {
                    System.out.print("□");
                } else if (load[i][j] == -2) {
                    if (i == 15 && j == 15) {
                        System.out.print("X");
                    } else {
                        System.out.print("@");
                    }
                } else if (load[i][j] == -1) {
                    System.out.print("■");
                } else if (load[i][j] == 2) {
                    System.out.print("$");
                }
            }
            System.out.println();
        }
        while (!queue.isEmpty()) {
            System.out.println(Arrays.toString(queue.poll()));
        }
    }
 
    public static int[] changeQueue(Queue<int[]> queue) {
        // 큐의 마지막 값 전까지 앞의 모든 값을 다시 자기자신에게 offer함으로써 가장 늦게 넣은 갑을 poll해주는 메서드
        int cnt = 0;
        int size = queue.size();
        int[] temp = null;
        while (cnt != size) {
            temp = queue.poll();
            if (++cnt == size) {
                return temp;
            } else
                queue.offer(temp);
        }
        return temp;
    }
}