프로그래머스 - 빛의 경로 사이클

30분 내로 풀 거를 이해 잘못해서 3시간 가량 소비한 문제 `_'

단편적인 것만 보고 거기에 맞추느라 고생했다.

 

https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

 

문제에 중요한 힌트가 하나 있는데

한 격자에서 들어오고 나가는 방향은 언제나 똑같음.

이게 무슨 말이냐면 시작을 왼쪽위에서 아래서부터 하든, 오른쪽 아래에서 위에서부터 하든

도달하는 순서만 다를 뿐이지, 반드시 해당 방향으로 간다는 의미

ex) 아래서 들어오고 오른쪽에서 나간다면, 다른 방향으로 나가는 경우는 없다.

 

코드는 다음과 같은 방식으로 작성했다.

1. 전체 grid와 각 칸들의 4방향(상하좌우)에 대한 3차원 배열을 만든다.

2. 어떤 칸에서 나간 경로는 1.에서 만든 3차원 배열에 표시를 해두고, 카운트 1 증가

3. 만약 나간 경로가 이전에 나갔던 경로인 경우 현재까지 센 카운트 저장

4. 도착한 칸의 정보에 따라 방향을 바꿈

5. 1.에서 만든 3차원 배열의 모든 요소에 표시가 됐으면 저장한 카운트 정보들 오름차순해 반환

 

코드는 접어놨다.

import java.util.*;
class Solution {
    // R, C // 오른쪽, 아래, 왼쪽, 위쪽(오른쪽 방향 기준)
    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    char[][] map;
    boolean[][][] visit;
    int gridRLen, gridCLen;
    ArrayList<Integer> answer = new ArrayList();
    
    public ArrayList<Integer> solution(String[] grid) {
        gridRLen = grid.length;
        gridCLen = grid[0].length();
        
        init(grid);
        for(int r = 0; r < gridRLen; r++) {
            for(int c = 0; c < gridCLen; c++) {
                for(int d = 0; d < 4; d++) {
                    if(visit[r][c][d])
                        continue;
                    int ret = search(r, c, d);
                    if(ret > 0)
                        answer.add(ret);
                }
            }
        }
        Collections.sort(answer);
        return answer;
    }
    
    public int search(int r, int c, int d) {
        int count = 0;
        while(true) {
            if(visit[r][c][d])
                break;
            visit[r][c][d] = true;
            //System.out.print(" / r = " + r + " c = " + c + " d = " + d);
            r = Math.floorMod(r + dir[d][0], gridRLen);
            c = Math.floorMod(c + dir[d][1], gridCLen);
            count++;
            if(map[r][c] == 'R')
                d = Math.floorMod(d + 1, 4);
            else if(map[r][c] == 'L')
                d = Math.floorMod(d - 1, 4);
        }
        //System.out.println();
        return count;
    }
    
    public void init(String[] grid) {
        visit = new boolean[gridRLen][gridCLen][4];
        map = new char[gridRLen][gridCLen];
        for(int i = 0; i < gridRLen; i++) {
            map[i] = grid[i].toCharArray();
        }
    }
}

 

 

 

이 밑으로는 잘못 생각했던 것들

시작점을 0,0으로만 잡으면 될 줄 알았었다.

 

1. 0, 0 부터 시작해 다시 0,0 으로 도착하면 되는 줄 알았다.

-> 1번 예시를 보면 0.0 부터 시작하지만, 0,0 엔 4번 도달하기 때문에 잘못된 생각

-> 사이클의 개념을 잘못 이해했다.

 

2. 0, 0 에서 나간 방향으로 돌아오면 되는 줄 알았다.

-> 일부만 보면 맞긴 하지만, 다른 칸을 기준으로 거기서 사이클이 먼저 만들어지는 경우,
0, 0까지 도달하느라 카운팅이 더 늘어남. 이 문제 외에도, 정답의 총 개수가 부족할 수 있다.

 

3. 어디든 root가 될 수 있는데 한 점만 root로 생각했다.

-> 좀 더 그려봤다면, 각 사이클마다 나가고 들어오는 경로가 다르단 걸 알 수 있었을 것이다.