Java 프로그래머스 빛의 경로 사이클 자바

 

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86052

프로그래머스

---

프로그래머스 빛의 경로 싸이클 문제

[문제 풀기 전 생각 정리]

• 문제를 요약하자면 다음과 같다.
  • 격자에 ‘S’가 있으면 이전 방향 그대로 직진.
  • 격자에 ‘L’이 있으면 좌회전
  • 격자에 ‘R’이 있으면 우회전.
  • 격자 밖으로 나가면 0으로 이동 (순환되는 구조).
• 사이클을 판단하는 방법은 같은 좌표를 같은 진행방향으로 재방문한 경우이다.
• 각 방향 별로 움직이는 메서드를 만들어 해당 방향에 맞게 호출한다.
• 위치정보를 가지는 클래스를 만들어 하나의 객체로 사용할 수 있게 한다.

[나의 풀이]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    // 방향을 나타내는 상수
    private static final char S = 'S';
    private static final char L = 'L';
    private static final char R = 'R';
    private static final int TO_DOWN  = 0;
    private static final int TO_UP    = 1;
    private static final int TO_LEFT  = 2;
    private static final int TO_RIGHT = 3;
    
    private char[][]      gridArr;    // 격자정보의 grid를 저장하는 2차원 배열
    private boolean[][][] isVisited;  // 빛이 방문했는지 여부를 저장하는 3차원 배열
    private int           xLength;    // 격자정보의 grid x축의 길이
    private int           yLength;    // 격자정보의 grid y축의 길이
    private List<Integer> answer;     // 각 경로의 길이를 저장하는 리스트

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

        xLength = grid.length;
        yLength = grid[0].length();

        gridArr = new char[xLength][yLength];
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                gridArr[i][j] = grid[i].charAt(j);
            }
        }

        isVisited = new boolean[xLength][yLength][4];
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                for (int k = 0; k < 4; k++) {
                    move(new Path(i, j, k, 0));
                }
            }
        }

        Collections.sort(answer);
        return answer.stream().mapToInt(i->i).toArray();
    }

    private void move(Path path) {
        while (!isVisited[path.x][path.y][path.direction]) {
            isVisited[path.x][path.y][path.direction] = true;

            if (gridArr[path.x][path.y] == S) {
                path = moveStraight(path);
            } else if (gridArr[path.x][path.y] == R) {
                path = moveRight(path);
            } else if (gridArr[path.x][path.y] == L) {
                path = moveLeft(path);
            }

            path.count++;
        }

        if (path.count > 0) {
            answer.add(path.count);

        }
    }

    private Path moveLeft(Path path) {
        if (path.direction == TO_DOWN) {
            path.y = (path.y + 1) % yLength;
            path.direction = TO_RIGHT;

            return path;
        }

        if (path.direction == TO_UP) {
            path.y = (path.y + yLength - 1) % yLength;
            path.direction = TO_LEFT;

            return path;
        }

        if (path.direction == TO_RIGHT) {
            path.x = (path.x + xLength - 1) % xLength;
            path.direction = TO_UP;

            return path;
        }

        path.x = (path.x + 1) % xLength;
        path.direction = TO_DOWN;

        return path;
    }

    private Path moveRight(Path path) {
        if (path.direction == TO_DOWN) {
            path.y = (path.y + yLength - 1) % yLength;
            path.direction = TO_LEFT;

            return path;
        }

        if (path.direction == TO_UP) {
            path.y = (path.y + 1) % yLength;
            path.direction = TO_RIGHT;

            return path;
        }

        if (path.direction == TO_RIGHT) {
            path.x = (path.x + 1) % xLength;
            path.direction = TO_DOWN;

            return path;
        }

        path.x = (path.x + xLength - 1) % xLength;
        path.direction = TO_UP;
        return path;
    }

    private Path moveStraight(Path path) {
        if (path.direction == TO_DOWN) {
            path.x = (path.x + 1) % xLength;

            return path;
        }

        if (path.direction == TO_UP) {
            path.x = (path.x + xLength - 1) % xLength;

            return path;
        }

        if (path.direction == TO_RIGHT) {
            path.y = (path.y + 1) % yLength;

            return path;
        }

        path.y = (path.y + yLength - 1) % yLength;
        return path;
    }

    class Path {
        int x;
        int y;
        int direction;
        int count;

        public Path(int x, int y, int direction, int count) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.count = count;
        }
    }
}

• line 21 : 주어진 grid를 받아서 각 위치에서 가능한 모든 방향으로 움직인 후 이동경로의 길이를 리턴한다.
• line 47 : move 메서드는 주어진 경로에서 다음 위치로 이동하게 한다. 위치 이동에 따라 방향 변경을 위해 moveStraight(직진), moveRight(오른쪽), moveLeft(왼쪽) 메서드를 호출한다.
• line 63 : 경로 순회를 마치면 길이를 저장한다.
• moveStraight, moveRight, moveLeft 각 메서드 별로 현재 위치에서 메서드에 명명된 방향대로 이동 후, 그다음 위치를 계산한다.
• line 146 : 위치, 방향, 이동 횟수를 Path 클래스의 형태로 저장한다.

[다른 사람의 풀이]

import java.util.ArrayList;

public class Solution {
    static int R, C;                                         // 행(Row), 열(Column)
    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 }; // 아래, 왼, 위, 오른
    static boolean[][][] isVisited;

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

        R = grid.length;
        C = grid[0].length();

        isVisited = new boolean[R][C][4];
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                for (int d = 0; d < 4; d++) {
                    if (!isVisited[i][j][d])
                        answer.add(light(grid, i, j, d ));
                }
            }
        }

        return answer.stream().sorted().mapToInt(i -> i).toArray();
    }

    private static int light(String[] grid, int r, int c, int d) {
        int cnt = 0; // 이동거리

        while (true) {
            if (isVisited[r][c][d])
                break;

            cnt++;	// 거리증가
            isVisited[r][c][d] = true; // 방문처리

            if (grid[r].charAt(c) == 'L')
                d = d == 0 ? 3 : d - 1; // 좌회전
            else if (grid[r].charAt(c) == 'R')
                d = d == 3 ? 0 : d + 1; // 우회전

            r = (r + dr[d] + R) % R;
            c = (c + dc[d] + C) % C;
        }

        return cnt;
    }
}

• solution 메서드의 3중 for문으로, 빛의 방문 여부를 확인하며 light 함수를 호출해 빛의 경로의 길이를 계산하고 있다.
• light 메서드는 특정위치 (r, c)와 방향 d에서 시작해서 빛이 이동하는 경로의 길이를 계산한다.
• 이동 경로상에서 빛이 'L' 또는 'R' 칸에 도달할 때마다 방향을 조정하고, 그리드의 경계에 도달하면 반대편으로 이동.
• 이미 방문한 위치와 방향으로 다시 돌아오면, 경로의 길이를 반환.

[정리]

개인 피셜 난이도 : ★★★★★

레벨 2치고는 정말 어려웠던 문제였던 것 같다.

오랜 시간 걸려서 문제를 이해했고, 

각각의 케이스를 계속 생각해야하니 쉽지 않았다.

 

아직도 알고리즘에 대한 접근이 쉽지 않은데,

계속해서 문제를 풀고,

다른 사람들의 풀이들도 보면서,

사고를 확장하는 연습을 계속 해봐야겠다.

언제나 새로운 정보 공유와 잘못된 정보

비판/지적/태클은 환영입니다!

도움이 되셨다면 공감♥️, 댓글 부탁드려요:)

끝.