[JAVA] Stack를 사용한 깊이우선 탐색 (DFS) Stack제네릭 사용 X

 

Queue와 동일한 미로로 작성하였습니다. 

빨간선 1번, 핑크선 2번, 초록선 3번 순으로 깊이 너비탐색을 통해 탈출구를 찾습니다.

동일하게 stack 크기도 5로 설정하였고 깊이

package Day3;

import java.util.ArrayList;
import java.util.Arrays;

public class MroStack {
    static int[][] map = {{0,0,0,-1,0,0,0,-1}, {0,-1,0,-1,0,-1,0,-1}, {0,-1,0,-1,-1,-1,0,-1}, {0,0,0,0,0,0,0,-1}, {-1,-1,-1,0,-1,-1,-1,-1}, {0,0,-1,0,-1,0,0,-1}, {-1,0,0,0,-1,0,-1,-1}, {-1,-1,-1,0,0,0,0,0}};
    static String[] stack = new String [5];
    static ArrayList<String> log = new ArrayList<String>();
    static int cnt;
    static String start = "0,0";
    static String exit = "7,7";
    static String temp = "";

    public static void main(String[] args) throws OverflowIntQueueException, OverflowIntStackException {
        disp();
        push(start);
        log.add(start);
        while(!exit.equals(temp)){
            search(pop());
            System.out.print("현재위치 : " + temp + " ");
            System.out.print("stack : " + Arrays.toString(stack) + "\n");
        }
    }
    static void search(String str) throws OverflowIntStackException {
        String [] temp = str.split(",");
        int x = Integer.parseInt(temp[0]);
        int y = Integer.parseInt(temp[1]);
        for(int i = x-1;i<=x+1;i+=2){
            valid(i,y);
        }
        for(int j = y-1;j<=y+1;j+=2){
            valid(x,j);
        }
    }
    static void valid(int x, int y) throws OverflowIntStackException {
        String tmp = x + "," + y;
        if(x <0 || y <0) { }
        else if(x > 7 || y > 7) { }
        else if (map[x][y] == -1){ }
        else if (Arrays.asList(stack).contains(tmp)){ }
        else{
            if(!log.contains(tmp)) {
                temp = tmp;
                push(tmp);
            }
        }

    }
    static void disp(){
        for (int[] ints : map) {
            for (int anInt : ints) {
                if (anInt == -1)
                    System.out.print(" ■");
                else {
                    System.out.print(" □");
                }
            }
            System.out.println();
        }
    }
    static void push(String str) throws OverflowIntStackException{
        if(cnt >= stack.length-1)
            throw new OverflowIntStackException();
        stack[cnt++] = str;
    }
    static String pop() throws OverflowIntStackException{
        if(cnt <= 0)
            throw new OverflowIntStackException();
        String n = stack[cnt-1];
        log.add(n);
        stack[cnt--] = null;
        return stack[cnt];
    }
}

 

package Day3;

public class OverflowIntStackException extends Exception {
}