[프로그래머스] 빛의 경로 사이클 (java)

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

---

 

 

 

프로그래머스

 

 

문제 요약

 

2차원 배열 느낌으로 칸이 주어지고 각 칸마다 격자가 있다.

 

격자에는 빛이 동서남북에서 들어올 수 있다.

 

격자는 빛을 직진, 좌회전, 우회전 시킬 수 있다.

 

배열에 있는 모든 격자들에 대한 사이클 수를 구해라

 

 

나의 풀이

 

존재하는 모든 격자들에 대해 시작점으로 설정하고 해당 격자로부터 발생한 사이클을 구할 것이다.

 

하나의 격자에 대해 사이클을 구할 때 빛의 출처 4가지를 모두 활용해 탐색하여 사이클을 구한다.(동,서,남,북)

 

예를 들어 좌표 (1,1) 의 격자에 왔다고 쳤을 때 어디서 왔는지는 총 4방향인 것이고 이 4방향으로부터 시작했음을 모두 탐색해야 모든 사이클을 구할 수 있다.

 

주의점

 

1. (1,1) 에서 (2,1) 로 갔다면 (2,1) 입장에서는 서쪽으로부터 빛이 온 것이고 서쪽 출처의 (2,1) 에서 경로를 모두 탐색하나

 

(1,1) 에서 시작해 (2,1)을 지나도록 경로를 모두 탐색하나 같은 사이클이다.

 

이 부분을 필터링해주지 않으면 시간초과났다.

 

2. 격자 하나가 빛을 꺾는 각도는 격자가 받은 빛의 방향에 의존한다. 잘 하면 깔끔하게 이 부분을 구현할 수 있을텐데 하다보니 분기가 많아져 코드가 더러워졌다.

 

 

 

  

 

풀이 코드

 

import java.util.*;

public class 빛의경로사이클 {
    static Mirror[][] mirrors;
    public static int[] solution(String[] grid) {
        mirrors = new Mirror[grid.length][grid[0].length()];
        for (int i = 0; i < mirrors.length; i++) {
            for (int j = 0; j < mirrors[0].length; j++) {
                mirrors[i][j] = new Mirror(String.valueOf(grid[i].charAt(j)));
            }
        }
        for (int i = 0; i < mirrors.length; i++) {
            for (int j = 0; j < mirrors[0].length; j++) {
                loop(i, j, new History(), From.LEFT);
                loop(i, j, new History(), From.RIGHT);
                loop(i, j, new History(), From.BOTTOM);
                loop(i, j, new History(), From.TOP);
            }
        }
        return answerList.stream().mapToInt(value -> value).sorted().toArray();
    }

    private static final List<Integer> answerList = new ArrayList<>();

    private static void loop(int currentX, int currentY, History history, From from) {
        while (true) {
            if (history.size != 0
                    && history.xList.get(0) == currentX && history.yList.get(0) == currentY
                    && history.froms.get(0).equals(from)) {
                answerList.add(history.size);
                return;
            }
            if (mirrors[currentX][currentY].fromContains(from)) {
                return;
            }
            mirrors[currentX][currentY].addFrom(from);
            history.set(from, currentX, currentY);
            Direction direction = mirrors[currentX][currentY].direction;
            From to = direction.move(from);
            currentX = setPoint(currentX, to.x, mirrors.length);
            currentY = setPoint(currentY, to.y, mirrors[0].length);
            from = to;
        }
    }

    private static int setPoint(int current, int newValue, int range) {
        if (current + newValue < 0) {
            return range - 1;
        }
        if (current + newValue >= range) {
            return 0;
        }
        return current + newValue;
    }

    static class Mirror {
        Direction direction;
        Set<From> set = new HashSet<>();

        public void addFrom(From from) {
            set.add(from);
        }

        public boolean fromContains(From from) {
            return set.contains(from);
        }

        public Mirror(String direction) {
            this.direction = Direction.valueOf(direction);
        }
    }

    enum Direction {
        L, S, R;

        public From move(From from) {
            if (this.equals(L)) {
                return from.moveLeft();
            }
            if (this.equals(R)) {
                return from.moveRight();
            }
            return from.moveSt();
        }
    }

    enum From {
        TOP(-1, 0), BOTTOM(1, 0), LEFT(0, -1), RIGHT(0, 1);

        private final int x;
        private final int y;

        From(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public From moveLeft() {
            if (this.equals(TOP)) {
                return LEFT;
            }
            if (this.equals(BOTTOM)) {
                return RIGHT;
            }
            if (this.equals(LEFT)) {
                return BOTTOM;
            }
            return TOP;
        }

        public From moveRight() {
            if (this.equals(TOP)) {
                return RIGHT;
            }
            if (this.equals(BOTTOM)) {
                return LEFT;
            }
            if (this.equals(LEFT)) {
                return TOP;
            }
            return BOTTOM;
        }

        public From moveSt() {
            return this;
        }
    }

    static class History {
        List<From> froms = new ArrayList<>();
        int size = 0;
        List<Integer> xList = new ArrayList<>();
        List<Integer> yList = new ArrayList<>();

        public void set(From from, int x, int y) {
            this.froms.add(from);
            this.xList.add(x);
            this.yList.add(y);
            this.size++;
        }
    }
}