미로찾기(Decision Problem) 에 대해서 알아보자

미로찾기(Decision Problem)

Decision Problem 답이 yes or no 인 문제

미로 찾기에 대해서 알아보겠습니다.

현재 위치에서 출구까지 가는 경우는 2가지로 나눠집니다. 1) 현재 위치가 출구 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 경로

이것을 수도 코드로 표현하면 다음과 같습니다.

수도코드

boolean findPath(x,y)
if (x,y) is either on the wall or a visited cell  //1)
    return false;
else if (x,y) is the exit   // 2)
    return true;
else 
    mark (x,y) as a visited cell; // 3)
for each neighbouring cell(x',y') of (x,y) do
    if findPath(x',y')
        return true;
return false

수도 코드 풀이하면 다음과 같습니다. 1) 현재 좌표가 벽 또는 방문한 적이 있는지 체크 합니다. 2) 출구인지 체크합니다. 3) 방문 길을 기록 합니다. 4) 각각 근처의 셀을 방문합니다.

MazePath.java

/**
* 미로 길 찾기
**/
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) {
        return false;
    }else if (x == N -1 && y == N - 1){
        return true;
    }else{
        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;
        return  false;
    }
}
​
/**
* 미로 보여주기
**/
public static void printMazePath(){
    System.out.println("##############");
    for(int[] data : maze){
        System.out.printf("## ");
        for(int item : data){
            System.out.printf(String.format("%d", item));
        }
        System.out.println(" ##");
    }
    System.out.println("##############\n");
}

Main.java

public static void main(String[] args) {
   System.out.println(maze);
   findMazePath(0, 0);
   System.out.println(maze);
}

소스 설명

MazePath.java 은 Recursion을 활용한 예시로 미로 찾기를 구성하였습니다.

1) x, y 값을 받을 때 해당 값이 미로를 벗어나고 있지 않는지 체크합니다.

if (x < 0 || y < 0 || x >= N || y >= N){

2) 같은 공간을 지나가지 않기 하기 위해서는 지난 가기 전의 값인지 체크합니다.

if (maze[x][y] != PATHWAY_COLOUR)

3) 최종 출구는 N -1 의 좌표값을 갖고 있는지 체크하여 보여줍니다.

if (x == N -1 && y == N - 1)

4) 지나갈 길은 PATH_COLOR로 설정하고 북, 동, 남, 서 를 기준으로 Recursion 으로 지나갈 수 있는 길이 있는지 체크합니다.

끝까지 진행했을 때 지나갈 길이 없으면 return false을 호출하게 됩니다.

마무리

미로찾기에 대해서 막막했던 알고리즘이 간단히 해결되는 것을 경험하였습니다.

Decision Problem 처럼 Yes, No 값으로 구성된 것에 대한 로직을 구성 시 무한루프에 빠지지 않도록 주의하시면 무리 없이 로직 구성할 수 있을 것으로 예상됩니다.

본 포스트는 영리한프로그래밍을 위한 알고리즘 강좌(인프런)를 기반으로 작성되었습니다.