[Programmers Lv2, Java] 빛의 경로 사이클
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.
- 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
- 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
- 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.
예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.
이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.
https://school.programmers.co.kr/learn/courses/30/lessons/86052
이런 문제를 풀기 위해 먼저 "한 Edge는 한 Cycle에만 속한다." 라는 개념을 알아야한다.
처음 문제를 봤을 때, 모든 지점에서 출발하는 사이클을 구해야한다고 생각하지 않고 (0,0)에서 출발하는 경우만 구하면된다고 생각했다.
String[][] grid2d = new String[grid.length][grid[0].length()];
for(int y = 0 ; y < grid2d.length ; y++) {
String[] split = grid[y].split("");
for(int x = 0 ; x < split.length ; x++) {
grid2d[y][x] = split[x];
}
}
int[][] directive = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
boolean[] checked = new boolean[4];
List<Integer> cycles = new ArrayList<>();
for(int i = 0 ; i < checked.length ; i++) {
if(checked[i]) continue;
int[] dir = directive[i];
int[] startPos = new int[]{0, 0};
int gridXLength = grid2d[0].length;
int gridYLength = grid2d.length;
int cycleNum = 0;
do{
cycleNum++;
startPos[0] += dir[0];
startPos[0] = startPos[0] >= gridXLength ? 0 : (startPos[0] < 0 ? gridXLength-1 : startPos[0]);
startPos[1] += dir[1];
startPos[1] = startPos[1] >= gridYLength ? 0 : (startPos[1] < 0 ? gridYLength-1 : startPos[1]);
String cdir = grid2d[startPos[1]][startPos[0]];
if(cdir.equals("L")) dir = new int[]{dir[1], -dir[0]};
else if(cdir.equals("R")) dir = new int[]{-dir[1], dir[0]};
if(startPos[0] == 0 && startPos[1] == 0) {
for(int cycleChecker = i ; cycleChecker < checked.length ; cycleChecker++) {
if(directive[cycleChecker][0] == dir[0] && directive[cycleChecker][1] == dir[1])
checked[cycleChecker] = true;
}
}
}while(!(dir[0] == directive[i][0] && dir[1] == directive[i][1] && startPos[0] == 0 && startPos[1] == 0));
cycles.add(cycleNum);
}
int[] answer = new int[cycles.size()];
for(int register = 0 ; register < cycles.size() ; register++)
answer[register] = cycles.get(register);
return answer;
그게 위와 같은 코드인데,
- 1. (0, 0) 지점에서 4방향에 모두 사이클 테스트를 보내본다.
- 2. 사이클 테스트 중 시작 위치와 같은 곳에 도착했다면, 남은 테스트 사이클중에 겹치는게 있는지 확인한다.
※ 만약 겹치는게 있다면, 시작 순서만 다르고 같은 사이클일 테니까.
- 3. 겹치는게 있으면 flag를 true로 변경한 뒤 계속 사이클 크기를 측정한다.
- 4. 측정이 종료되면 cycles에 등록하고 ( 동적 Array로 사용 )
- 5. 사이클 테스트가 종료되면 List를 Array로 바꾼 후 리턴한다.
이 코드는 기본적으로 주어진 테스트케이스에 대해서는 모두 성공하지만,
(0, 0)에서 출발하는 경우만 테스트하기 때문에 그 외의 지점에서 생기는 사이클은 모두 구하지 못하기 때문에 실제 검토에서 1개의 성공사례도 얻지 못했다.
그래서, 문제를 제대로 읽고 이 코드를 grid2d의 x,y 모든 지점에 대해 테스트하게 확장했다.
public int[] solution(String[] grid) {
// 맵 만들기
String[][] grid2d = new String[grid.length][grid[0].length()];
for (int y = 0; y < grid2d.length; y++) {
String[] split = grid[y].split("");
for (int x = 0; x < split.length; x++) {
grid2d[y][x] = split[x];
}
}
// 4방향에 대한 테스트를 모두 진행
int[][] directive = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 각 좌표지점마다 방향에 대한 플래그 설치
boolean[][][] checked = new boolean[grid2d.length][grid2d[0].length][4];
// 각 사이클마다의 이동거리 리스트
List<Integer> cycles = new ArrayList<>();
for(int y = 0 ; y < grid2d.length ; y++) {
for(int x = 0 ; x < grid2d[0].length ; x++) {
for(int i = 0 ; i < 4 ; i++) {
// 이전 사이클에서 중복 사이클이 확인 된 경우 다음 방향 검사
if(checked[y][x][i]) continue;
// 방향 및 변수 초기화
int[] dir = directive[i];
int[] startPos = new int[]{x, y};
int gridXLength = grid2d[0].length;
int gridYLength = grid2d.length;
int cycleNum = 0;
// 최소 1번은 이동하므로, do-while로 진행, 시작 좌표 (x,y) 에서 같은방향으로 진행 하는 경우 사이클이 종료되었다고 판단한다.
checked[y][x][i] = true;
do {
cycleNum++;
// 진행 방향으로 한 칸 이동한다.
startPos[0] += dir[0];
startPos[0] = startPos[0] >= gridXLength ? 0 : (startPos[0] < 0 ? gridXLength - 1 : startPos[0]);
startPos[1] += dir[1];
startPos[1] = startPos[1] >= gridYLength ? 0 : (startPos[1] < 0 ? gridYLength - 1 : startPos[1]);
String cdir = grid2d[startPos[1]][startPos[0]];
if (cdir.equals("L")) dir = new int[]{dir[1], -dir[0]};
else if (cdir.equals("R")) dir = new int[]{-dir[1], dir[0]};
for (int cycleChecker = 0; cycleChecker < 4; cycleChecker++) {
int[] compareDir = directive[cycleChecker];
if (compareDir[0] == dir[0] && compareDir[1] == dir[1]) {
checked[startPos[1]][startPos[0]][cycleChecker] = true;
break;
}
}
} while (!(dir[0] == directive[i][0] && dir[1] == directive[i][1] && startPos[0] == x && startPos[1] == y));
cycles.add(cycleNum);
}
}
}
// 등록된 사이클을 array로 변환
int[] answer = new int[cycles.size()];
for (int register = 0; register < cycles.size(); register++)
answer[register] = cycles.get(register);
// 오름차순으로 정렬
Arrays.sort(answer);
return answer;
}
기본적인 틀은 모두 같은데, 달라진점은 플래그를 체크하는 과정에서 어차피 모든 포인트에서 시작하는 사이클을 검사해야하므로, 모든 이동과정에서 플래그를 Set하는 것으로 변경했다.
