BFS 너비 우선 탐색 Stack & Queue

1. Queue_ver

package week_4;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class BFS_LabyrinthSearch {
 
    public static void main(String[] args) {
        int[][] load = { { 0, 0, 0, 0, 0 }, { 0, -1, -1, -1, 0 }, { 0, 0, 0, -1, 0 }, { 0, -1, 0, -1, 0 },
                { 0, -1, 0, 0, 0 } };
        int x = 0; // x좌표
        int y = 0; // y좌표
        int[] end = { 2, 1 }; // 종료 위치
        Queue<int[]> queue = new LinkedList<>();
 
        queue.add(new int[] { 0, 0 });
 
        do {
 
            int[] ps = queue.poll();
            x = ps[1];// x좌표
            y = ps[0];// y좌표
 
            if (end[0] == y && end[1] == x) {
                System.out.println("정답 : " + y + " , " + x);
                load[y][x] = -2;
                break;
            }
            load[y][x] = -2;// 지나간 좌표
            if (x > 0) {// 현재위치의 x좌표가 x축 첫 좌표보다 크고
                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) {// 현재위치의 y좌표가 y축 첫 좌표보다 크고
                if (load[y - 1][x] >= 0) {// 위쪽 타일검색
                    load[y - 1][x] = 2;
                    queue.offer(new int[] { y - 1, x });
                }
            }
            if (y < load.length - 1) {// 현재위치의 y좌표가 y축 끝 좌표보다 작고
                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 == 2 && j == 1) {
                        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()));
        }
    }
 
}
 

2. Stack_ver

package week_4;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 
public class BFS_LabyrinthSearch {
 
    public static void main(String[] args) {
        int[][] load = { { 0, 0, 0, 0, 0 }, { 0, -1, -1, -1, 0 }, { 0, 0, 0, -1, 0 }, { 0, -1, 0, -1, 0 },
                { 0, -1, 0, 0, 0 } };
        int x = 0; // x좌표
        int y = 0; // y좌표
        int[] end = { 3, 2 }; // 종료 위치
        Stack<int[]> pop_stack = new Stack<>();
        Stack<int[]> push_stack = new Stack<>();
 
        push_stack.push(new int[] { 0, 0 });
 
        do {
            while (!push_stack.isEmpty()) {
                pop_stack.push(push_stack.pop());
            }
            int[] ps = pop_stack.pop();
            x = ps[1];// x좌표
            y = ps[0];// y좌표
 
            if (end[0] == y && end[1] == x) {
                System.out.println("정답 : " + x + " , " + y);
                load[y][x] = -2;
                break;
            }
            load[y][x] = -2;// 지나간 좌표는 -2로 세팅
            if (x > 0) {// 현재위치의 x좌표가 x축 첫 좌표보다 크고
                if (load[y][x - 1] >= 0) {// 왼쪽 타일값이 0보다 클 경우 =>>왼쪽 타일 검색
                    load[y][x - 1] = 2;
                    changeStack(push_stack, pop_stack);
                    push_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;
                    changeStack(push_stack, pop_stack);
                    push_stack.push(new int[] { y, x + 1 });
                }
            }
 
            if (y > 0) {// 현재위치의 y좌표가 y축 첫 좌표보다 크고
                if (load[y - 1][x] >= 0) {// 위쪽 타일검색
                    load[y - 1][x] = 2;
                    changeStack(push_stack, pop_stack);
                    push_stack.push(new int[] { y - 1, x });
                }
            }
            if (y < load.length - 1) {// 현재위치의 y좌표가 y축 끝 좌표보다 작고
                if (load[y + 1][x] >= 0) {// 아래쪽 타일검색
                    load[y + 1][x] = 2;
                    changeStack(push_stack, pop_stack);
                    push_stack.push(new int[] { y + 1, x });
                }
            }
 
            if (push_stack.isEmpty() && pop_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 == 3 && j == 2) {
                        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();
        }
    }
 
    public static void changeStack(Stack<int[]> push_stack, Stack<int[]> pop_stack) {// 스택에서 pop을 하는순간 다른 스택으로 모든 값을
                                                                                        // 넘겨주면서 역순으로 정렬
        while (!pop_stack.isEmpty()) {
            push_stack.push(pop_stack.pop());
        }
    }
 
}