[알고리즘/인프런정리] 2-1. Recursion의 응용: 미로찾기

- Decision Problom 문제이다. (답이 YES/NO)

현재 위치에서 출구까지 가는 경로의 조건

1. 현재 위치가 출구이거나

2. 이웃셀 중 하나에서 현지 위치를 지나지 않고 출구까지 가는 경로가 있거나

인접 셀이 방문했던 셀인 경우 무한루프에 빠지게 된다.

방문했던 셀을 표시하는 것이 중요하다.

수도 코드

boolean findPath(x,y)
    if(x,y) is either on the wall or a visited cell
        return false;
    else if(x,y) is the exit // base case (탈출점인 경우)
        return true;
    else
        mark (x,y) as a visited cell; // 방문 표시
        for each neighbouring cell (x',y') or (x,y) do // x,y 인접 셀들 방문
            if findpath(x',y')
                return true; // 도착점을 찾아서(else if구문) 뒤로 리턴 true 되는 경우
            else
                return false;

미로 찾기 문제 : class Maze

public class 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_COLOUR = 0; // white
    private static final int WALL_COLOUR = 1;     // blue
    private static final int BLOCKED_COLOUR = 2;  // red
    private static final int PATH_COLOUR = 3;     // green

    public static boolean findMazePath(int x, int y) {
        // 작성
    }
}

PATHWAY_COLOUR : not visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell

WALL_COLOUR : 통과 못하는 길

BLOCKED_COLOUR : visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell (방문해본 셀)

PATH_COLOUR : 출구 가능성이 있는 길 (방문해본 셀)

어떤 셀을 발견하면 일단 PATH_COLOUR 로 칠한 후, BLOCKED인지 판단함.

 

코드 풀이

github

package recursion;

/* 재귀 - 미로찾기 */

public class Miro_201004 {
    public static void main(String[] args) {
        Maze.printMaze();
        System.out.println("----------------------------");
        Maze.findMazePath(0,0);
        System.out.println("----------------------------");
        Maze.printMaze();
    }
}

class 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_COLOUR = 0; // white
    private static final int WALL_COLOUR = 1;     // blue
    private static final int BLOCKED_COLOUR = 2;  // red
    private static final int PATH_COLOUR = 3;     // green

    public static boolean findMazePath(int x, int y) {

        if(x < 0 || y < 0 || x >= N || y >= N) return false;
        else if(maze[x][y] != PATHWAY_COLOUR) { // x,y가 이동할 수 있는 경로인 경우 탐색할 필요 없음
            return false;
        }else if(x==(N-1) && y==(N-1)){ // 도착점인 경우
            maze[x][y] = PATH_COLOUR;
            return true;
        }else { // 그렇지 않은 일반적인 경우
            System.out.println("path_colour [" + x + ", " + y + "]");
            maze[x][y] = PATH_COLOUR;
            if(findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePath(x,y-1)) {
                return true;
            }
            maze[x][y] = BLOCKED_COLOUR; // dead end
            return false;
        }
    }

    public static void printMaze() {
        for(int i=0; i<maze.length; i++) {
            for(int j=0; j<maze[0].length; j++) {
                System.out.print(maze[i][j] + ", ");
            }
            System.out.println();
        }
    }
}