Count Luck

문제: Count Luck

난이도: Medium

 

문제 설명

 N x M의 그리드에서 ‘X’는 지나갈 수 없는 나무, ‘.’은 지나갈 수 있는 길, ‘M’은 현재 위치, ‘*’은 도착 지점이라고 정한다. 헤르미온느는 마법의 지팡이를 사용해 갈림길에서 반드시 정확한 방향을 찾아낼 수 있다. 론은 헤르미온느가 마법의 지팡이를 몇 번 사용할지(k)를 예상하였다. 론이 정확하게 맞췄다면 “Impressed”를, 못 맞췄다면 “Oops”를 출력하게 하여라.

 예를 들어 그리드가 다음과 같이 주어졌을 경우

 

↓

두 번째 그림과 같이 마법의 지팡이를 3번 사용한다. 따라서 론이 예상한 횟수인 k가 3이면 “Impressed”를, 3이 아니면 “Oops를 출력하게 한다.”

 

문제 해결

소스 코드

 public static int rowMax;
    public static int colMax;
    public static boolean foundFlag;
    public static int result;

    static String countLuck(String[] matrix, int k) {
        int row=0;
        int col=0;
        rowMax = matrix.length;
        colMax = matrix[0].length();
        foundFlag = false;
        result = 0;
        char[][] grid = new char[rowMax][colMax];
        String resultStr;

        for(int i = 0; i < rowMax; i++) {
            for(int j = 0; j < colMax; j++) {
                grid[i][j] = matrix[i].charAt(j);
                if(matrix[i].charAt(j)=='M') {
                    row = i;
                    col = j;
                }
            }
        }

        dfs(grid, row, col);

        if(result==k) {
            resultStr = "Impressed";
        } else {
            resultStr = "Oops!";
        }

        return resultStr;
    }

    static void dfs(char[][] m, int row, int col) {
        int branchChk = 0;

        if(m[row][col]=='*') {
            foundFlag = true;
            return;
        }

        if(row-1>=0 && (m[row-1][col] == '.'||m[row-1][col] == '*')) {
            branchChk++;
        }
        if(col+1<colMax && (m[row][col+1] == '.'||m[row][col+1] == '*')) {
            branchChk++;
        }
        if(row+1<rowMax && (m[row+1][col] == '.'||m[row+1][col] == '*')) {
            branchChk++;
        }
        if(col-1>=0 && (m[row][col-1] == '.'||m[row][col-1] == '*')) {
            branchChk++;
        }

        if(branchChk>1 && !foundFlag) {
            m[row][col] = 'Y';
            result++;
        } else {
            m[row][col] = 'N';
        }
       
        if(row-1>=0 && (m[row-1][col] == '.'||m[row-1][col] == '*')) {
            dfs(m, row-1, col);
        }
        if(col+1<colMax && (m[row][col+1] == '.'||m[row][col+1] == '*')) {
            dfs(m, row, col+1);
        }
        if(row+1<rowMax && (m[row+1][col] == '.'||m[row+1][col] == '*')) {
            dfs(m, row+1, col);
        }
        if(col-1>=0 && (m[row][col-1] == '.'||m[row][col-1] == '*')) {
            dfs(m, row, col-1);
        }

        if(!foundFlag && m[row][col] == 'Y') {
            m[row][col] = 'N';
            result--;
        }
    }

 

 

해설

 처음에는 최단거리를 구하는 방법을 응용하기 위해 BFS(너비우선탐색) 알고리즘을 사용하였으나, 수 차례의 실패를 경험하고 안 되겠다 싶어서 DFS(깊이우선탐색) 알고리즘으로 전환하였다.

 dfs 메소드는 다음 네 가지 행동을 하여 지팡이를 사용한 수를 구한다.

 첫 번째, 현재 위치가 도착지점이면 flag를 true로 변경하고 리턴한다.

 두 번째, 현재 위치에서 갈림길이 있는지를 확인한다. 갈림길이 있다면 현재 위치의 값을 ‘Y’로 변경한 후 지팡이를 사용한 수를 저장한 변수의 값을 증가시키고, 없다면 ‘N’으로 바꿔 중복 탐색을 없앤다.

 세 번째, 현재 탐색하는 경로에서 다음으로 갈 수 있는 곳이 있는지를 찾는다.

 네 번째, flag가 false이고, 현재 위치가 ‘Y’라면 현재 위치의 값을 ‘N’으로 바꾸고, 지팡이를 사용한 횟수를 감소시킨다. 이는 잘못된 경로의 갈림길을 체크 해놓은 것을 없애는 작업이다.

 dfs가 모든 재귀호출을 멈추고 종료되면 실제로 지팡이를 사용한 횟수가 구해진다. 남은 건 이 값이 k와 같은지 아닌지를 비교하여 두 가지 문자열 중 하나를 리턴하는 일 뿐이다.