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

문제 설명

 

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

 

접근 방법

우선 각각의 빛의 경로 사이클을 구분하는 방법은 특정 노드 위치(행 : row, 열 : col)에서의 특정 방향(동, 서, 남, 북)을 통해 구분하는 방법이 있습니다. 예를 들어 A 사이클과 B 사이클이 있다고 했을 때 A 사이클의 모든 노드에서의 방향이 B 사이클의 각각의 모든 노드에서의 방향은 중복되는 것이 하나도 없습니다. (A[i][j][k] != B[i][j][k]) 만일 하나라도 같다면 A 사이클과 B 사이클은 같은 사이클일 수밖에 없는 것입니다.

 

이러한 점을 고려하여 모든 특정 노드 위치에서의 모든 방향들을 완전 탐색하여 빛의 경로 사이클을 구할 수 있는데, 이때 탐색시마다 특정 노드에서의 특정 방향에 대해 방문할 때마다 방문처리를 해주면 다음 사이클을 탐색 시에 중복되지 않고 사이클을 탐색할 수 있습니다. 이러한 특정 노드 위치(행 : row, 열 : col)에서의 특정 방향(direction : 0, 1, 2, 3)에 대한 방문 처리 정보는 3차원 boolean형 배열을 통해 나타낼 수 있습니다.

 

하나의 사이클 탐색을 종료시키기 위한 조건으로는 맨 처음 노드의 위치와 방향을 기억해놓았다가(startPonints) 추후 탐색 시 동일한 위치와 방향을 가리킬 경우 종료시키도록 했습니다. 참고로 해당 문제를 재귀함수를 통해 정답을 도출하려고 했으나, 런타임 에러(Stack Overflow)가 나와, 반복문으로 접근했습니다.

 

 

전체 소스 코드

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

class Solution {

    List<Integer> list = new ArrayList<>();
    boolean[][][] visited;
    char[][] g;
    int row, col;
    int[] startPoints = new int[3];

    public int[] solution(String[] grid) {
        row = grid.length;
        col = grid[0].length();
        g = new char[row][col];
        visited = new boolean[row][col][4];

        for (int i = 0; i < row; i++) {
            g[i] = grid[i].toCharArray();
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < 4; k++) { // direction → 0 : up, 1 : right, 2 : down, 3 : left
                    if (!visited[i][j][k]) {
                        startPoints[0] = i;
                        startPoints[1] = j;
                        startPoints[2] = k;
                        move(i, j, k);
                    }
                }
            }
        }

        Collections.sort(list);

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private void move(int row, int col, int direction) {
        int count = 0;

        while (true) {
            visited[row][col][direction] = true;

            if (direction == 0) {
                if (g[row][col] == 'S') {
                    row--;
                } else if (g[row][col] == 'R') {
                    col++;
                    direction = 1;
                } else if (g[row][col] == 'L') {
                    col--;
                    direction = 3;
                }
            } else if (direction == 1) {
                if (g[row][col] == 'S') {
                    col++;
                } else if (g[row][col] == 'R') {
                    row++;
                    direction = 2;
                } else if (g[row][col] == 'L') {
                    row--;
                    direction = 0;
                }
            } else if (direction == 2) {
                if (g[row][col] == 'S') {
                    row++;
                } else if (g[row][col] == 'R') {
                    col--;
                    direction = 3;
                } else if (g[row][col] == 'L') {
                    col++;
                    direction = 1;
                }
            } else if (direction == 3) {
                if (g[row][col] == 'S') {
                    col--;
                } else if (g[row][col] == 'R') {
                    row--;
                    direction = 0;
                } else if (g[row][col] == 'L') {
                    row++;
                    direction = 2;
                }
            }

            if (row < 0) {
                row = this.row - 1;
            } else if (row > this.row - 1) {
                row = 0;
            } else if (col < 0) {
                col = this.col - 1;
            } else if (col > this.col - 1) {
                col = 0;
            }

            count++;

            if (startPoints[0] == row && startPoints[1] == col && startPoints[2] == direction) {
                list.add(count);
                break;
            }
        }
    }
}

 

참고자료

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