[86052] 빛의 경로 사이클

✔ 빛의 경로 사이클

[프로그래머스 86052]

문제 분석하기

상하좌우 4 방향으로 한 번씩 빛을 쏘며 같은 경로를 이용하지 않았는지 확인

이때 방문 배열에 어느 방향(위에서 아래, 아래에서 위, 왼쪽에서 오른쪽, 오른쪽에서 왼쪽)에서 왔는지도 함께 작성

또한 배열 밖으로 나간 경우라면 반대편으로 이동시켜주어야 함

 

방향이 0(아래), 1(왼쪽), 2(위쪽), 3(오른쪽)일 때

1. 진입 노드가 'S'인 경우

직진하므로 0 → 0,  1 → 1,  2 → 2,  3 → 3 방향으로 이동

2. 진입 노드가 'L'인 경우

좌회전하므로 0 → 3, 1 → 0, 2 → 1, 3 → 2

3. 진입 노드가 'R'인 경우

우회전하므로 0 → 1, 1 → 2, 2 → 3, 3 → 0

손으로 풀어보기

1. 상하좌우 4 방향으로 한 번씩 빛을 쏜 후, 같은 경로를 이용하지 않았는지 확인하며 빛의 경로 사이클 구하기
2. 이때 방문 배열에 어느 위치에 어느 방향으로 빛이 왔는지도 함께 저장
3. 이후 좌회전 또는 우회전이라면 빛을 꺾어야 함
   • 방향이 0(아래), 1(왼쪽), 2(위쪽), 3(오른쪽)일 때
   • 좌회전 : 다음 방향 = (현재 방향 + 3) % 4
   • 우회전 : 다음 방향 = (현재 방향 + 1) % 4
4. 만약 배열 밖으로 나간 경우라면 반대편으로 이동시켜주도록 함
5. 빛이 이동할 수 있는 경로 사이클을 정렬한 후 반환

슈도코드 작성하기

grid(격자의 정보)
answer(격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 저장하는 리스트)
visited(방문 유무 배열)
for(i -> grid만큼) {
    for(j -> grid[0]만큼) {
        for(d -> 4만큼) {
            if(visited[i][j][k]를 방문하지 않았다면)
                answer에 move(grid, i, j, d) 저장
        }
    }
}
answer을 정렬하고 배열로 변환하여 반환

move {
    dx, dy(아래쪽, 왼쪽, 위쪽, 오른쪽 상화좌우 좌표)
    count(빛의 경로 사이클의 길이)
    while(true) {
        if(visited[i][j][d]가 방문했다면)
            break
        count 증가
        visited[i][j][d]를 방문 처리
        if('L'이라면)
            좌회전이므로 d = (d + 3) % 4
        else if('R'이라면)
            우회전이므로 d = (d + 1) % 4
        만약 배열 밖으로 나간 경우라면 반대편으로 이동시켜주기 위해 
        i = (i + dx[d] + grid.length) % grid.legth
        j = (j + dy[d] + grid[0].length) % grid[0].legth
    }
    count 반환
}

코드 구현하기

/**
 * 86052) 빛의_경로_사이클
 */
public class L069_86052 {
    boolean[][][] visited;

    // grid(격자의 정보)
    public int[] solution(String[] grid) {
        // answer(격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 저장하는 리스트)
        ArrayList<Integer> answer = new ArrayList<>();
        // visited(방문 유무 배열)
        visited = new boolean[grid.length][grid[0].length()][4];
        // 모든 칸에서 4가지 방향으로 빛 쏘기
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length(); j++) {
                for (int d = 0; d < 4; d++) {
                    // visited[i][j][k]를 방문하지 않았다면
                    if (!visited[i][j][d])
                        // answer에 move(grid, i, j, d) 저장
                        answer.add(move(grid, i, j, d));
                }
            }
        }
        // answer을 정렬하고 배열로 변환하여 반환
        return answer.stream().sorted().mapToInt(Integer::intValue).toArray();
    }

    // 빛 움직이기
    private Integer move(String[] grid, int i, int j, int d) {
        // dx, dy(아래쪽, 왼쪽, 위쪽, 오른쪽 상화좌우 좌표)
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        // count(빛의 경로 사이클의 길이)
        int count = 0;
        while (true) {
            // visited[i][j][d]를 이미 방문했다면
            if (visited[i][j][d])
                break;
            // count 증가
            count++;
            // visited[i][j][d]를 방문 처리
            visited[i][j][d] = true;
            // 좌회전이라면
            if (grid[i].charAt(j) == 'L')
                d = (d + 3) % 4;
            // 우회전이라면
            else if (grid[i].charAt(j) == 'R')
                d = (d + 1) % 4;
            // 만약 배열 밖으로 나간 경우라면 반대편으로 이동시켜주기 위해 갱신
            i = (i + dx[d] + grid.length) % grid.length;
            j = (j + dy[d] + grid[0].length()) % grid[0].length();
        }
        // count 반환
        return count;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L069_86052 solution = new L069_86052();

        String[] grid = { "SL", "LR" };

        int[] result = solution.solution(grid);

        System.out.println(Arrays.toString(result));
    }
}