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

0.  문제 링크

 

 

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

프로그래머스

---

1.  풀이 방법

 

 

1. 일단 문제에서 체크해야 되는 요소가 방향, 위치, 다음 경로이다.
2. 사실 방향, 위치, 다음 경로는 구현의 영역이기 때문에 개인 역량에 따라 달라진다.
3. 아무튼 우리는 사이클을 확인해야 하는데, 나는 추가적으로 check를 사용해서 해결했다.
4. check는 [y 좌표][x 좌표][4방향]으로 확인하는데, 특정 좌표에서 특정 방향으로 간 적이 있다면 True로 표시한다.
5. 어떤 좌표에 도착해서, 해당 좌표의 방향대로 가려고 하는데 check에 이미 True로 되어 있다면 그것은 사이클이다.
6. 따라서 모든 좌표와 모든 방향을 탐색하면서 Cycle을 찾음과 동시에 check를 갱신한다. 이러면 모든 사이클을 찾고, 길이도 찾을 수 있다.

---

2.  코드

 

 

def solution(grid):
    def rotation(y, x, d):      # 방향 전환을 하는 로직
        if grid[y][x] == 'S':
            return d
        elif grid[y][x] == 'R':
            return (d + 1) % 4
        else:
            return (d - 1) % 4
    
    
    def cycle(y, x, d):
        length = 1      # 일단은 맨 처음 쏴보긴 해야됨.
        check[y][x][d] = True       # 해당 위치에서 해당 방향으로 빛을 쏜 적이 있음
        curY, curX = (y + dir[d][0]) % h, (x + dir[d][1]) % w       # 빛이 한 칸 이동함. 끝이라면 반대로 이동함.
        curD = rotation(curY, curX, d)      # 해당 칸에서 빛이 방향 전환을 함.
        
        while not (curY == y and curX == x and curD == d):      # 모든 값이 같으면 사이클인 것임
            length += 1
            check[curY][curX][curD] = True
            curY, curX = (curY + dir[curD][0]) % h, (curX + dir[curD][1]) % w
            curD = rotation(curY, curX, curD)
        
        return length
    

    answer = []
    
    h = len(grid)
    w = len(grid[0])
    check = [[[False] * 4 for _ in range(w)] for _ in range(h)]     # 특정 좌표에서 특정 방향으로 나간 적 있는지
    dir = {0 : [-1, 0], 1 : [0, 1], 2 : [1, 0], 3 : [0, -1]}
    
    for i in range(h):
        for j in range(w):
            for d in range(4):
                if not check[i][j][d]:      # 해당 방향으로 빛을 내보낸 적이 없다면
                    answer.append(cycle(i, j, d))
    
    answer.sort()       # 정렬
    return answer

---

3.  마무리