빛의 경로 사이클 - 월간 코드 챌린지 시즌3 (Java, Level 2)

 

처음 풀이

 

1. grid를 각 격자별로 나눠서 2차원 배열에 저장한다.(map),

   격자 1개당 up, right, down, left 시계 방향에 대한 정보를 담을 3차원 배열을 만든다.

 

2. 현재 이동방향과 격자에 따라 이동하면서 재귀적으로 경로 길이를 저장하는 메소드를 만든다. (move)

- 재귀중단조건은 현재 이동하는 경로에 저장된 값이 0이 아닌 경우이다. 이미 지나간 경로이기 때문이다.

- 재귀중단조건을 만났다는 건 하나의 순환 경로가 만들어진 것이므로 현재까지 이동거리를 list에 저장한다.

 

3. 현재 이동방향과 도착할 다음 격자에 따라 다음 이동방향을 결정하는 메소드를 만든다. (changeDir)

- "S"면 방향 그대로, "L"이면 반 시계 방향이므로 현재 direction index에서 이전 index 값, "R"이면 시계 방향이므로 현재 direction index에서 다음 index 값

 

4. row, column, direction index 등 값을 더하고 빼면서 일정 범위를 벗어날 가능성이 있는 변수를 범위 안의 값으로 후처리 해주는 메소드. (makeInRange)

 

 

solution()

- 모든 격자의 모든 방향을 출발점으로 잡고 move() 호출

-> 단, 현재 저장된 정보 값이 0이 아닐 때만! (즉, 순환 경로에 포함되지 않은 경로에 대해서만)

 

//up, right, down, left 방향 순
final int[] DIRECTION_ROW = {-1, 0, 1, 0};
final int[] DIRECTION_COL = {0, 1, 0, -1};
//격자 map
String[][] map;
//격자 1개당 up, right, down, left 순으로 경로 저장할 배열
int[][][] route;
//순환 경로 길이 저장할 list
List<Integer> answerList;

public int[] solution(String[] grid) {
    answerList = new ArrayList<>();

    //grid를 2차원 배열(변수 map)로
    int row = grid.length;
    int col = grid[0].length();

    map = new String[row][col];
    for (int i = 0; i < row; i++) {
        map[i] = grid[i].split("");
    }//for end

    route = new int[row][col][4];

    //모든 경로에 대해서 move()호출
    //단, 현재 값이 0이 아닌 경우 - 즉, 순환 경로에 포함되지 않은 경로에서만!
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            for (int k = 0; k < 4; k++) {
                if (route[i][j][k]==0) {
                    move(i, j, row, col, 1, k);
                }
            }//for end
        }//for end
    }//for end

    int answerSize = answerList.size();
    int[] answer = new int[answerSize];
    for (int i = 0; i < answerSize; i++) {
        answer[i] = answerList.get(i);
    }//for end

    Arrays.sort(answer);

    return answer;
}//solution() end

 

move()

//현재 이동방향과 격자에 따라 이동하면서 재귀적으로 경로 길이 저장하는 method
public void move(int nowRow, int nowCol, int row, int col, int length, int dirIndex) {
    //지나갔던 경로라면 순환경로가 완성되었으므로
    //총 길이 저장
    if (route[nowRow][nowCol][dirIndex]!=0) {
        answerList.add(length-1);
        return;
    }

    //현재까지 경로길이 저장
    route[nowRow][nowCol][dirIndex] = length;

    //다음 격자로 이동
    int newRow = nowRow + DIRECTION_ROW[dirIndex];
    int newCol = nowCol + DIRECTION_COL[dirIndex];

    //범위 벗어나는 row, col 값 후처리
    newRow = makeInRange(newRow, row);
    newCol = makeInRange(newCol, col);

    //다음 격자에서의 새로운 이동방향
    int newDirIndex = changeDir(map[newRow][newCol], dirIndex);

    move(newRow, newCol, row, col, length+1, newDirIndex);
}//move() end

 

changeDir()

//격자와 현재 방향에 따른 새로운 방향 index 리턴
public int changeDir(String point, int dirIndex) {
    switch (point) {
        case "L": dirIndex--;
        break;
        case "R": dirIndex++;
        break;
    }
    return makeInRange(dirIndex, 4);
}//changeDir() end

 

makeInRange()

//범위 벗어나는 값 후처리하는 method
public int makeInRange(int now, int range) {
    return (now==range)? 0 : (now==-1)? range-1 : now;
}

 

 

결과를 보니 테스트 7번만 런타임 에러가 떴다.

 

 

다른 풀이

3중 for문에서 move()를 실행해도 되는지 검사는 전부 다 하지만, 실제 move()를 실행하는 경우는 많지 않을 거라 생각했다. 

그래서 너무 많은 재귀로 인해 StackOverFlow로 런타임 에러가 뜨는게 아닐까 싶어 while문으로 수정했다.

move() 내부를 그대로 옮겨와 3중 for문 안에 넣었다.

 

//모든 경로에 대해서 move()호출
//단, 현재 값이 0이 아닌 경우 -> 즉, 순환 경로에 포함되지 않은 경로에서만!
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        for (int k = 0; k < 4; k++) {
            if (route[i][j][k]==0) {
                int nowRow = i;
                int nowCol = j;
                int length = 1;
                int dirIndex = k;

                while (true) {
                    //0이 아니란 뜻은 이미 체크된 경로란 뜻이므로 break
                    if (route[nowRow][nowCol][dirIndex]!=0) {
                        answerList.add(length-1);
                        break;
                    }
                    //현재까지 경로길이 저장
                    route[nowRow][nowCol][dirIndex] = length;

                    //다음 격자로 이동
                    nowRow = nowRow + DIRECTION_ROW[dirIndex];
                    nowCol = nowCol + DIRECTION_COL[dirIndex];

                    //범위 벗어나는 row, col 값 후처리
                    nowRow = makeInRange(nowRow, row);
                    nowCol = makeInRange(nowCol, col);

                    //다음 격자에서의 새로운 이동방향
                    dirIndex = changeDir(map[nowRow][nowCol], dirIndex);

                    length++;
                }//while end
            }
        }//for end
    }//for end
}//for end

 

 

통과했다!