Recursion - 미로찾기

2021/03/01 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (1)

2021/03/01 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (2)

2021/03/02 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (3)

2021/03/04 - [개발/알고리즘 기초공부] - Recursion - Blob 셀 카운트

 

import java.util.Arrays;

public class Maze {
    public static void main(String[] args) throws Exception {
        System.out.println(Arrays.deepToString(maze)); 
        findPath(0,0);
        System.out.println(Arrays.deepToString(maze)); 
    }

    private static int N=8;
    private static int[][] maze = {
        {0,0,0,0,0,0,0,1},
        {0,1,1,0,1,1,0,1}, 
        {0,0,0,1,0,0,0,1},
        {0,1,0,0,1,1,0,0},
        {0,1,1,1,0,0,1,1},
        {0,1,0,0,0,1,0,1},
        {0,0,0,1,0,0,0,1},
        {0,1,1,1,0,1,0,0},
    };
    private static final int PATHWAY_COLOR = 0; //white
    //private static final int WALL_COLOR = 1;  //blue
    private static final int BLOCKED_COLOR = 2; //red  visited이며 출구까지의 경로상에 있지 않음이 밝혀진 셀
    private static final int PATH_COLOR = 3;    //green visited이며 출구로 가는 경로가 될 가능성이 있는 셀


    //현재 위치에서 출구까지 가는 경로가 있으려면
    //1. 현재 위치가 출구이거나
    //2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
    public static boolean findPath (int x, int y){
        if ( x<0 || y<0 || x >= N || y>= N ) return false;
        else if (maze[x][y] != PATHWAY_COLOR) return false;
        else if (x == N-1 && y == N-1){
            maze[x][y] = PATH_COLOR;
            return true;
        }
        else {
            maze[x][y] = PATH_COLOR;
            if (findPath(x-1, y)||findPath(x, y-1)||findPath(x+1, y)||findPath(x, y+1)){
                return true;
            }
            maze[x][y] = BLOCKED_COLOR;
            return false;
        }
    }
}

1. 맵 좌표에서 벗어난 좌표인경우 false

2. 해당좌표가 벽이거나 이미 지나온길이면 false

3. 출구좌표인 경우 green으로 표기하고 true 반환

4. 어느 것도 해당되지 않으면 green 표기하고, 순환함수로 true를 찾아가면 true반환

    길을 찾지 못한 경우면 red 표기하고, false 반환