[프로그래머스] 월간 코드 챌린지 시즌 3 - 빛의 경로 사이클 (Java)

 

문제 링크

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

문제 설명

각 칸마다 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'로 이루어져 있습니다.

 

입출력 예

grid	result
["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.
• 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

---

풀이

 

char[][] map : 격자(grid) 정보를 가지는 2차원 배열

char[][][] visited : 방문 여부를 체크하는 3차원 배열. 3번째 배열은 위치정보를 나타냄.

 

같은 위치의 칸에 도달하더라도 다른 방향에서 오는 것은 다른 접근으로 고려해야하기 때문에 3차원 배열로 나타내려고 했다.

grid를 통해 받아낸 모든 칸의 네 방향에 대해 move() 메소드를 실행시켜 사이클을 찾아내도록 구현했다.

 

사이클이 존재한다는 건 이미 방문했던 칸에 방문했던 방향으로 접근함을 의미한다. move() 내에서 탐색을 시도하면서 vistied를 통해 접근 여부를 체크해두고, 이미 방문한 경우 탐색을 종료하고 사이클 길이를 리턴한다.

 

현재 경로의 위치, 방향, 길이의 정보를 Path라는 객체로 묶어서 관리하도록 하였고, 탐색을 하는 과정에서 객체를 계속 생성해내는 건 메모리 이슈가 존재할 수 있을 거 같아 넘겨받은 인스턴스를 재활용하였다.

 

다음 칸을 결정하는 요인은 칸(map)에 적힌 키워드(S, L, R)과 접근 방향이다. 키워드와 접근 방향에 따라 다음 이동해야할 칸이 어디인지 달라지기 때문에 현재 칸의 키워드와 접근 방향을 고려해 이동시키는 moveStraight(), moveLeft(), moveRight() 메소드를 구현하였다. 

 

사이클의 길이는 ArrayList에 저장하였고, 마지막에 int[]로 변경하기 전에 오름차순으로 정렬해주는 과정이 필요하다.

 

move()의 탐색 방식을 재귀 방식으로 구현했더니 테스트 7에서 런타임에러가 발생했다. 재귀 방식이 아닌 반복문으로 고쳐서 돌려보니 통과되었다.

 

(객체지향적으로 코드를 작성하고자 했으나 시간 등을 고려하다보니 객체지향적으로 작성되다 만 애매한 코드가 탄생한 것 같다..)

 

 

코드

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 DIRECTION_TO_DOWN = 0;
    private static final int DIRECTION_TO_UP = 1;
    private static final int DIRECTION_TO_LEFT = 2;
    private static final int DIRECTION_TO_RIGHT = 3;
    private char[][] map;
    private boolean[][][] visited;
    private int xLength;
    private int yLength;
    pirvate List<Integer> answer;


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

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

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

        visited = 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 (!visited[path.x][path.y][path.direction]) {
            visited[path.x][path.y][path.direction] = true;

            if (map[path.x][path.y] == S) {
                path = moveStraight(path);
            } else if (map[path.x][path.y] == R) {
                path = moveRight(path);
            } else if (map[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 == DIRECTION_TO_DOWN) {
            path.y = (path.y + 1) % yLength;
            path.direction = DIRECTION_TO_RIGHT;

            return path;
        }

        if (path.direction == DIRECTION_TO_UP) {
            path.y = (path.y + yLength - 1) % yLength;
            path.direction = DIRECTION_TO_LEFT;

            return path;
        }

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

            return path;
        }

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

        return path;
    }

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

            return path;
        }

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

            return path;
        }

        if (path.direction == DIRECTION_TO_RIGHT) {
            path.x = (path.x + 1) % xLength;
            path.direction = DIRECTION_TO_DOWN;

            return path;
        }

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

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

            return path;
        }

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

            return path;
        }

        if (path.direction == 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;
        }
    }
}