1 ★★★ [프로그래머스][JAVA] 빛의 경로 사이클 (배열, 구현..?, 재귀를 while문으로)

220606

실수

1. 오름차순을 내림차순으로 착각

2. Line:48~50

            nr = makeRow(nr, nDir);
            nc = makeCol(nc, nDir);
            nDir = makeDir(nr, nc, nDir);

 

이 부분을 

            nr = makeRow(nr, dir);
            nc = makeCol(nc, dir);
            nDir = makeDir(nr, nc, dir);

이렇게 실수함.. 하 ㅠ

 

import java.util.*;
 
class Solution {
    private static boolean[][][] isPassed;
    // [0]↑ [1]→ [2]↓ [3]←
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};
    private static List<Integer> answerList;
    private static int R, C;
    private static String[] grid;
    
    public Integer[] solution(String[] gridInput) {
        grid = gridInput;
        isPassed = new boolean[grid.length][grid[0].length()][4];
        answerList = new ArrayList<>();
        R = grid.length;
        C = grid[0].length();
        
        for(int r=0; r<R; r++){
            for(int c=0; c<C; c++){
                for(int dir=0; dir<4; dir++){
                    checkCycle(r,c,dir);
                }
            }
        }
        
        Collections.sort(answerList);
        // answerList.forEach(System.out::println);
 
        return answerList.toArray(new Integer[0]);
    }
    
    private void checkCycle(int r, int c, int dir){
        int startR = r;
        int startC = c;
        int startDir = dir;
        isPassed[startR][startC][startDir] = true;
        int cycleNum = 1;
        
        int nr = r;
        int nc = c;
        int nDir = dir;
        
        
        while(true){
            // System.out.println(nr+" "+nc+" "+nDir);
            
            nr = makeRow(nr, nDir);
            nc = makeCol(nc, nDir);
            nDir = makeDir(nr, nc, nDir);
            
            
            
            if(nr==startR && nc==startC && nDir==startDir){
                answerList.add(cycleNum);
                break;
            }
            else if(isPassed[nr][nc][nDir]){
                break;
            }
            isPassed[nr][nc][nDir] = true;
            cycleNum++;
        }
        // System.out.println(nr+" "+nc+" "+nDir);
        // System.out.println();
    }
    
    private int makeRow(int r, int dir){
        int nr = r + dr[dir];
        if(nr<0){
            nr = R-1;
        }
        else if(nr>=R){
            nr = 0;
        }
        return nr;
    }
    
    private int makeCol(int c, int dir){
        int nc = c + dc[dir];
        if(nc<0){
            nc = C-1;
        }
        else if(nc>=C){
            nc = 0;
        }
        return nc;
    }
    
    private int makeDir(int r, int c, int dir){
        char currChar = grid[r].charAt(c);
        switch(currChar){
            case 'S' :
                return dir;
            case 'L' :
                return (dir-1<0)?3:dir-1;
            case 'R' :
                return (dir+1>=4)?0:dir+1;
        }
        
        return dir;
    }
}

---

 

 

 

요약 : 문제 이해 못함.. 주어진 문제를 빨리 파악하고 규칙 빨리 찾기 필요, 테케7번 재귀 때문에 stackOverFlow RuntimeException일어나서 while문으로 고쳐야함

 

코딩은 스스로 했지만 문제 풀이 방식은 질문하기탭 뒤져서 찾았음..

문제 이해를 못했음 빛의 사이클이라는 개념을 이해를 못했는데

주어진 격자테이블의 어떠한 격자를 고르던, 빛이 시작하는 방향을 어떤 방향으로 고르던간에

반드시 시작한 격자와 빛의 방향으로 돌아오게 되있음( 여기까진 이해했는데 )

 

사이클이라는 개념이 이해 안갔음 사이클이 여러개 있고 1개 있는 경우가 있는데 이건 도대체 뭐지 싶었음

 

알고보니 격자테이블이 주어진 상황에서

임의의 격자로부터 임의의 방향으로 빛을 쏠 때, 그 빛의 경로를 색칠을 한다는 개념으로 칠해보면(화살표의 방향포함)

앞서 말한대로 처음 시작한 격자의 시작한 방향과 일치하는 순간이 오는데

그 전까지의 빛의 경로가 한 싸이클이라는 의미임 이해하는데 너무 힘들었다..ㅠㅠ

 

여기서 더 중요한 것이 하나 있는데

방금 위에서 싸이클 하나를 그렸다고 가정할 때, 

또 다른 임의의 격자에서 임의의 방향으로 빛을 쏘는 싸이클을 그리다가

앞서 미리 그려 놓은 싸이클의 경로 위에 있으면 그건 같은 싸이클이라는 의미라는거임..

 

import java.util.*;

class Solution {
    private static boolean[][][] isVisited;
    private static char[][] grid;
    // [0]↑ [1]→ [2]↓ [3]←
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};
    private static List<Integer> answerList;
    
    public int[] solution(String[] gridStr) {
        int r = gridStr.length;
        int c = gridStr[0].length();
        isVisited = new boolean[r][c][4]; 
        grid = new char[r][c];
        answerList = new ArrayList<>();
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                grid[i][j] = gridStr[i].charAt(j);
                // System.out.print(grid[i][j]+" ");
            }
            // System.out.println();
        }
        
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                setStartPoint(i, j);
            }
        }
        
        // answerList.forEach(System.out::println);
        Collections.sort(answerList);
        int[] answer = new int[answerList.size()];
        for(int i=0; i<answerList.size(); i++){
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
    
    private void setStartPoint(int startRow, int startCol){
        for(int i=0; i<4; i++){
            if(!isVisited[startRow][startCol][i]){
                int newRow = (startRow+dr[i]<0)? startRow+dr[i]+grid.length:
                              (grid.length<=startRow+dr[i])? startRow+dr[i]-grid.length
                                                                :startRow+dr[i];
                int newCol = (startCol+dc[i]<0)? startCol+dc[i]+grid[0].length:
                              (grid[0].length<=startCol+dc[i])? startCol+dc[i]-grid[0].length
                                                                :startCol+dc[i];
                isVisited[startRow][startCol][i] = true;
                findCycle(newRow, newCol, i, startRow, startCol, i, 1);
            }
        } 
    }
    
    private void findCycle(int currRow, int currCol, int preI, int startRow, int startCol, int startI, int accumNum){
        int i = (grid[currRow][currCol]=='S')? preI : 
                (grid[currRow][currCol]=='L')? (preI+3)%4 : (preI+1)%4;
        
        if(currRow==startRow && currCol==startCol && i==startI){
            answerList.add(accumNum);
            return;
        }
                
        if(!isVisited[currRow][currCol][i]){
            int newRow = (currRow+dr[i]<0)? currRow+dr[i]+grid.length:
                          (grid.length<=currRow+dr[i])? currRow+dr[i]-grid.length
                                                            :currRow+dr[i];
            int newCol = (currCol+dc[i]<0)? currCol+dc[i]+grid[0].length:
                          (grid[0].length<=currCol+dc[i])? currCol+dc[i]-grid[0].length
                                                            :currCol+dc[i];
            isVisited[currRow][currCol][i] = true;
            findCycle(newRow, newCol, i, startRow, startCol, startI,accumNum+1);
        }        
    }
}

 

근데 테케7번에 에러남

 

 

알고보니 재귀로 풀어서 stackOverFlow 런타임에러 뜬거였음

재귀를 while문으로 고쳐줘야함..ㅠㅠ

 

 

 

 

import java.util.*;

class Solution {
    private static boolean[][][] isVisited;
    private static char[][] grid;
    // [0]↑ [1]→ [2]↓ [3]←
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};
    private static List<Integer> answerList;
    
    public int[] solution(String[] gridStr) {
        int r = gridStr.length;
        int c = gridStr[0].length();
        isVisited = new boolean[r][c][4]; 
        grid = new char[r][c];
        answerList = new ArrayList<>();
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                grid[i][j] = gridStr[i].charAt(j);
                // System.out.print(grid[i][j]+" ");
            }
            // System.out.println();
        }
        
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                findCycle(i, j);
            }
        }
        
        // answerList.forEach(System.out::println);
        Collections.sort(answerList);
        int[] answer = new int[answerList.size()];
        for(int i=0; i<answerList.size(); i++){
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
    
    private void findCycle(int startRow, int startCol){
        Loop:
        for(int i=0; i<4; i++){
            if(!isVisited[startRow][startCol][i]){
                isVisited[startRow][startCol][i] = true;
                int accumNum = 1;
                
                int newRow = (startRow+dr[i]<0)? startRow+dr[i]+grid.length:
                              (grid.length<=startRow+dr[i])? startRow+dr[i]-grid.length
                                                                :startRow+dr[i];
                int newCol = (startCol+dc[i]<0)? startCol+dc[i]+grid[0].length:
                              (grid[0].length<=startCol+dc[i])? startCol+dc[i]-grid[0].length
                                                                :startCol+dc[i];
                int newI = (grid[newRow][newCol]=='S')? i : 
                           (grid[newRow][newCol]=='L')? (i+3)%4 : (i+1)%4;
                
                while( !(newRow==startRow && newCol==startCol && newI==i) ){
                    if(isVisited[newRow][newCol][newI]){
                        continue Loop;
                    }
                    isVisited[newRow][newCol][newI] = true;
                    accumNum++;
                    
                    newRow = (newRow+dr[newI]<0)? newRow+dr[newI]+grid.length:
                              (grid.length<=newRow+dr[newI])? newRow+dr[newI]-grid.length
                                                                :newRow+dr[newI];
                    newCol = (newCol+dc[newI]<0)? newCol+dc[newI]+grid[0].length:
                              (grid[0].length<=newCol+dc[newI])? newCol+dc[newI]-grid[0].length
                                                                :newCol+dc[newI];
                    newI = (grid[newRow][newCol]=='S')? newI : 
                           (grid[newRow][newCol]=='L')? (newI+3)%4 : (newI+1)%4;
                }
                answerList.add(accumNum);
            }
        } 
    }
    
//     private void findCycle(int currRow, int currCol, int preI, int startRow, int startCol, int startI, int accumNum){
        // int i = (grid[currRow][currCol]=='S')? preI : 
        //         (grid[currRow][currCol]=='L')? (preI+3)%4 : (preI+1)%4;
        
//         if(currRow==startRow && currCol==startCol && i==startI){
//             answerList.add(accumNum);
//             return;
//         }
                
//         if(!isVisited[currRow][currCol][i]){
//             int newRow = (currRow+dr[i]<0)? currRow+dr[i]+grid.length:
//                           (grid.length<=currRow+dr[i])? currRow+dr[i]-grid.length
//                                                             :currRow+dr[i];
//             int newCol = (currCol+dc[i]<0)? currCol+dc[i]+grid[0].length:
//                           (grid[0].length<=currCol+dc[i])? currCol+dc[i]-grid[0].length
//                                                             :currCol+dc[i];
//             isVisited[currRow][currCol][i] = true;
//             findCycle(newRow, newCol, i, startRow, startCol, startI,accumNum+1);
//         }        
//     }
}