[프로그래머스, Java] 빛의 경로 사이클

🔗 문제 링크

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

🤔 문제

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

📌 제한사항

• 1 ≤ grid의 길이 ≤ 500
  • 1 ≤ grid의 각 문자열의 길이 ≤ 500
  • grid의 모든 문자열의 길이는 서로 같습니다.
  • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

😮 문제 해결 방법

각 노드의 진입 경로 (상, 하, 좌, 우)에서 빛이 들어온 경우를 모두 판단하고, 이미 해당 진입 경로로 들어온 경우를 만나면 사이클이 있다고 판단하면 된다.

즉, 방문하지 않은 모든 노드 및 방향에 대해 BFS를 진행해주고, 각 노드의 “S”,”L”,”R” 에 따라 다음 노드의 진입 방향을 결정해 주기만 하면 된다.

그리고 빛이 격자의 마지막에 다다른 경우 반대쪽 끝으로 오는 경우만 체크해주면 된다.

하나의 노드에서 상, 하, 좌, 우 방향을 방문했는지 모두 체크해주어야 하므로 방문 배열은 3차원 배열(행, 열, 방향)으로 선언해서 방문처리여부를 판단한다.

먼저 각 노드의 진입 방향 별 다음 노드의 방향이 어떻게 결정되는지 확인한다.

1. 상,하,좌,우 방향을 각각 0, 1, 2, 3으로 본다.

2. 진입 노드 방향 별 다음 노드 진입 방향 판단

   1. 진입 노드가 “S”인 경우

      

   2. 진입 노드가 “L”인 경우

      

   3. 진입 노드가 “R”인 경우

      

진입 노드의 “S”, “L”, “R” 별 다음 노드 진입 방향을 표로 정리해보면 아래와 같다.

	“S”	“L”	“R”
상 (0)	상 (0)	좌 (2)	우 (3)
하 (1)	하 (1)	우 (3)	좌 (2)
좌 (2)	좌 (2)	상 (0)	상 (0)
우 (3)	우 (3)	하 (1)	하 (1)

두번째로, 다음 진입 노드가 끝을 넘어간 경우 판단

1. 현재 노드의 진출 방향이 마지막 행(n-1) 의 하단인 경우 다음 노드의 진입 방향은 첫번째 행 ‘0(상)’ 방향
   1. 진입 방향이 상단 (0)이고 현재 노드가 “S”
   2. 진입 방향이 우측 (3)이고 현재노드가 “L”
   3. 진입 방향이 좌측 (2)이고 현재노드가 “R”
   4. 다음 노드의 nextRow = 0
2. 현재 노드의 진출 방향이 첫번재 행의 상단인 경우 다음 노드의 진입 방향은 마지막 행(n-1)의 ‘1(하)’ 방향
   1. 진입 방향이 하단 (1)이고 현재노드가 “S”
   2. 진입 방향이 좌측 (2)이고 현재노드가 “L”
   3. 진입 방향이 우측 (3)이고 현재노드가 “R”
   4. 다음 노드의 nextRow = n-1
3. 현재 노드의 진출 방향이 마지막 열(n-1)의 우측인 경우 다음 노드의 진입 방향은 첫번째 열의 ‘2(좌)’ 방향
   1. 진입 방향이 좌측 (2)이고 현재노드가 “S”
   2. 진입 방향이 하단 (1)이고 현재노드가 “R”
   3. 진입 방향이 상단 (0)이고 현재노드가 “L”
   4. 다음 노드의 nextCol = 0
4. 현재 노드의 진출 방향이 첫번째 열의 좌측인 경우 다음 노드의 진입 방향은 마지막 열(n-1)의 ‘3(우)’ 방향
   1. 진입 방향이 우측 (3)이고 현재노드가 “S”
   2. 진입 방향이 하단 (1)이고 현재노드가 “L”
   3. 진입 방향이 상단 (2)이고 현재노드가 “R”
   4. 다음 노드의 nxtCol = n-1

마지막으로, 빛이 노드에 진입할 때마다 방문 처리를 해주고, 진출할 때마다 사이클 횟수를 증가시키고, 다음 노드의 진입 방향이 이미 방문한 방향이면 사이클 횟수를 정답배열에 넣어준다.

🚩 Java 코드

package com.algorithm.Programmers.Lv2;

import java.util.*;

public class Solution_86052_빛의_경로_사이클 {
    public static void main(String[] args) {
        String[] grid = {"R","R"};
        int[] solution = solution(grid);
        for (int x : solution) System.out.println("x = " + x);
    }
    static class Point {
        private int row;
        private int col;
        private int dir;

        public Point(int row, int col, int dir) {
            this.row = row;
            this.col = col;
            this.dir = dir;
        }

        public int getRow() {
            return row;
        }

        public int getCol() {
            return col;
        }

        public int getDir() {
            return dir;
        }
    }
    private static String[][] map;
    private static boolean[][][] visited;
    private static int[] solution(String[] grid) {
        map = new String[grid.length][grid[0].length()];
        visited = new boolean[grid.length][grid[0].length()][4];
        List<Integer> answerList = new ArrayList<>();

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length(); col++) {
                map[row][col] = String.valueOf(grid[row].charAt(col));
            }
        }
        for(int row = 0; row< map.length; row++) {
            for(int col = 0; col < map[row].length; col++){
                // 0 : 상, 1: 하, 2: 좌, 3: 우
                for(int direction = 0; direction < 4; direction++) {
                    if(!visited[row][col][direction]) {
                        answerList.add(searchPath(row, col, direction));
                    }
                }
            }
        }
        Collections.sort(answerList);
        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }

    private static int searchPath(int row, int col, int direction) {
        int count = 0;
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(row, col, direction));

        while(!queue.isEmpty()) {
            Point point = queue.poll();
            int curX = point.getRow();
            int curY = point.getCol();
            int curDir = point.getDir();

            if(visited[curX][curY][curDir]) return count;
            visited[curX][curY][curDir] = true;

            // 다음 노드 진입 방향 구하기
            Point next = nextPath(curX, curY, curDir);

            // 다음 노드 큐에 추가
            queue.add(new Point(next.getRow(), next.getCol(), next.getDir()));

            // 진입한 노드 갯수 증가
            count++;
        }

        return count;
    }

    // 다음 노드 진입 방향 구하기
    private static Point nextPath(int curX, int curY, int curDir) {
        int nextRow = curX;
        int nextCol = curY;
        int nextDir = curDir;

        // 현재 노드 진입 방향 별 다음 노드 진입 방향
        if((map[curX][curY].equals("S") && curDir ==0) || (map[curX][curY].equals("L") && curDir == 3) || (map[curX][curY].equals("R") && curDir == 2)) {
            nextRow = curX +1;
            nextDir = 0;
        }
        else if((map[curX][curY].equals("S") && curDir ==1) || (map[curX][curY].equals("L") && curDir == 2) || (map[curX][curY].equals("R") && curDir == 3)) {
            nextRow = curX -1;
            nextDir = 1;
        }
        else if((map[curX][curY].equals("S") && curDir ==2) || (map[curX][curY].equals("L") && curDir == 0) || (map[curX][curY].equals("R") && curDir == 1)) {
            nextCol = curY +1;
            nextDir = 2;
        }
        else {
            nextCol =  curY-1;
            nextDir = 3;
        }

        // 다음 노드의 행 혹은 열이 범위 밖으로 벗어나는 경우 체크
        if(checkEndpoint(nextRow, nextCol)) {
            if(nextDir == 0) {
                nextRow = 0;
            }
            else if(nextDir == 1) {
                nextRow = map.length-1;
            }
            else if(nextDir == 2) {
                nextCol = 0;
            }
            else {
                nextCol = map[nextRow].length-1;
            }
        }
        return new Point(nextRow, nextCol, nextDir);
    }

    private static boolean checkEndpoint(int nextRow, int nextCol) {
        return nextRow < 0 || nextRow >= map.length || nextCol < 0 || nextCol >= map[nextRow].length;
    }
}