문제 링크

문제 간단 해석

격자 내의 빛이 순환하는 길의 길이를 찾아 정렬하여 반환하는 문제. 2단계에서 가장 정답률이 낮다.

Java

풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    class Point {
        private int y;
        private int x;
        private int t;
        
        public Point(int y, int x, int t) {
            this.y = y;
            this.x = x;
            this.t = t;
        }
        
        public int getY() {
            return y;
        }
        
        public int getX() {
            return x;
        }
        
        public int getT() {
            return t;
        }
    }
    
    public int cycle(int now, int std) {
        if (now == std)
            return 0;
        else if (now == -1)
            return std - 1;
        
        return now;
    }
    
    public int[] solution(String[] grid) {
        int row = grid.length, col = grid[0].length();
        boolean[][][] field = new boolean[row][col][4];
        int[] dy = {0, 1, 0, -1}, dx = {1, 0, -1, 0};
        Deque<Point> deque = new ArrayDeque<>();
        Point start, now;
        int y, x, t;
        List<Integer> answer = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        map.put('S', 0);
        map.put('L', -1);
        map.put('R', 1);
        
        for (int r = 0; r < row; r++)
            for (int c = 0; c < col; c++)
                check: for (int to = 0; to < 4; to++) {
                    if (field[r][c][to])
                        continue;
                    
                    deque.clear();
                    y = r;
                    x = c;
                    t = to;
                    
                    do {
                        deque.addLast(new Point(y, x, t));
                        y = cycle(y + dy[t], row);
                        x = cycle(x + dx[t], col);
                        t = cycle(t + map.get(grid[y].charAt(x)), 4);

                        if (field[y][x][t])
                            continue check;
                        
                    } while (y != r || x != c || t != to);
                    
                    answer.add(deque.size());
                    
                    while (!deque.isEmpty()) {
                        now = deque.removeLast();
                        field[now.getY()][now.getX()][now.getT()] = true;
                    }
                }
        
        return answer.stream().sorted().mapToInt(i->i).toArray();
    }
}

해석

Point class 해석은 스킵.

public int cycle(int now, int std) {
    if (now == std)
        return 0;
    else if (now == -1)
        return std - 1;
    
    return now;
}

기준을 넘어서는 값을 기준 내의 값으로 변환시키는 함수.

boolean[][][] field = new boolean[row][col][4];
...
Map<Character, Integer> map = new HashMap<>();
map.put('S', 0);
map.put('L', -1);
map.put('R', 1);

field를 생성. 각 격자 공간마다 4개의 진행방향에 대한 길을 만든다. 해당 길을 지나쳤는지, 아닌지로 갈 수 있는 길과 없는 길을 판단할 것이기에 boolean으로.

S, L, R에 대한 방향 상대값을 설정. 시계방향 기준으로 L은 -1, R은 +1.

for (int r = 0; r < row; r++)
    for (int c = 0; c < col; c++)
        check: for (int to = 0; to < 4; to++) {
            if (field[r][c][to])
                continue;
            ...

마지막 for문에 check 태그를 걸어준다.
만약 이번에 살펴보는 길이 이미 지나친 길이라면 스킵.

deque.clear();
y = r;
x = c;
t = to;

do {
    deque.addLast(new Point(y, x, t));
    y = cycle(y + dy[t], row);
    x = cycle(x + dx[t], col);
    t = cycle(t + map.get(grid[y].charAt(x)), 4);

    if (field[y][x][t])
        continue check;
    
} while (y != r || x != c || t != to);

answer.add(deque.size());

while (!deque.isEmpty()) {
    now = deque.removeLast();
    field[now.getY()][now.getX()][now.getT()] = true;
}

길을 확인하기 전에, deque를 깔끔히 비워 연산시의 에러를 없애자(참고로 deque는 stack처럼 사용될 것).
현재 위치를 볼 y, x, t에 값을 넣어준다.

deque에 현재 위치를 추가, 현재 방향 t 기준으로 전진하여 y와 x를 갱신한다. cycle 함수를 사용하여 범위 내의 값으로 변경.
t는 전진하여 도착한 위치의 글자에 따라 증감되니, 해당하는 위치 글자를 얻어오고 범위 내 값으로 변경.

만약 다음에 전진할 길이 이미 전에 지나친 길이라면?
똑같은 사이클이 만들어질테니 check 태그 붙인 반복문을 다시 진행시킨다.

이번에 도착하여 다음에 진행할 길이 스타트 지점과 같은 길이라면, 빛의 사이클 하나를 구한 것이다.

answer에 현재 deque 길이를 넣어 빛의 사이클 길이를 기록.

deque가 빌 때까지 하나씩 빼오면서 지나온 길들을 true로 변경시킨다.

return answer.stream().sorted().mapToInt(i->i).toArray();

answer를 정렬 후 int map 변경, Array로 변환 후 return.

Python

풀이 코드

def solution(grid):
    row = len(grid)
    col = len(grid[0])
    area = [[[True] * 4 for _ in range(col)] for _ in range(row)]
    
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    direction = {'S': 0, 'L': -1, 'R': 1}
    answer = []
    
    for r in range(row):
        for c in range(col):
            for step in range(4):
                y = r
                x = c
                to = step
                route = []
                
                while True:
                    if len(route) != 0 and y == r and x == c and to == step:
                        for route_r, route_c, route_to in route:
                            area[route_r][route_c][route_to] = False
                        answer.append(len(route))
                        break
                        
                    if not area[y][x][to]:
                        break
                        
                    route.append([y, x, to])
                    y = (y + dy[to]) % row
                    x = (x + dx[to]) % col
                    to = (to + direction[grid[y][x]]) % 4
    
    return sorted(answer)

해석

Java와 대동소이하므로 메인 알고리즘만 확인하겠다.

while True:
    if len(route) != 0 and y == r and x == c and to == step:
        for route_r, route_c, route_to in route:
            area[route_r][route_c][route_to] = False
        answer.append(len(route))
        break
        
    if not area[y][x][to]:
        break
        
    route.append([y, x, to])
    y = (y + dy[to]) % row
    x = (x + dx[to]) % col
    to = (to + direction[grid[y][x]]) % 4

route에 값이 있고 (처음에는 무조건 한번 돌린다는 얘기) 현재 위치가 시작점과 같다면 빛의 사이클 하나를 구했으니 해당하는 길들을 False로 만들어 더 이상 진행할 수 없게 하고 route의 길이만큼 답에 넣어준다.

만약 가지 못 하는 길이라면 break한다.

y, x, to를 변환한다. Java와는 달리 음수값이 나와도 배열의 역방향으로 탐색 가능하기에 해당 식이 성립된다.

여담

오늘 아침에 보니 프로그래머스 사이트가 개편되어 정답률의 높낮이를 한 번에 볼 수 있게 되었다.
좋은 변화라 생각한다. 정답률 낮은 것부터 블로그에 작성하려 생각중.
그러다 너무 쉬운 것들이 나오면 3단계로 빨리 올라가는 게 나을 것 같다.
눈에 이상이 생겨 다음 문제는 병원 다녀와서 작성해야겠다.