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

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

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

 

사이클은 전체를 분할 한다.

즉, A 하고 B 사이클이 있을 때, A = B 이거나 A ∩ B = Φ 이다.

하나의 사이클의 원소는 grid[][] 에서 가지는 방향(상, 하, 좌, 우)라고 할 수 있다.

 

1. grid[][] 에서 상(-1, 0), 하(1, 0), 좌(0, -1), 우(0, 1) 를 시작으로 사이클을 만든다.

 

2. dic 의 key 는 grid[][] 의 좌푯값이고 value 는 해당 grid[][] 에서 빛이 이동했던 방향이다(list). dic[(i, j)] 에 k(방향) 이 있다면 이미 사이클로써 answer 에 값이 저장되었기 때문에 무시한다.

 

3. 없다면, 반복문을 돌려서 dic[] 에 중복되는 값이 생길 때까지(= 사이클이 끝날 때까지) 움직이는 경로마다 result 를 1씩 더하여 result 를 answer 에 담는다.

 

4. answer 를 sort() 하여 반환한다.

 

from collections import defaultdict

def solution(grid):
    answer = []
    grid = list(map(lambda x : list(x), grid))
    n, m = len(grid), len(grid[0])
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    dic = defaultdict(list)

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in d:
                if k not in dic[(i, j)]:
                    d1, d2 = k
                    x, y = i, j
                    result = 0
                    
                    while (d1, d2) not in dic[(x, y)]:
                        result += 1
                        dic[(x, y)].append((d1, d2))
                        x += d1
                        y += d2

                        if x == -1: x = n - 1
                        if x == n: x = 0
                        if y == -1: y = m - 1
                        if y == m: y = 0

                        s = grid[x][y]

                        if s == 'L': d1, d2 = (d2, d1) if d1 != 0 else (-d2, -d1)
                        if s == 'R': d1, d2 = (-d2, -d1) if d1 != 0 else (d2, d1)

                    answer.append(result)
    
    answer.sort()
    
    return answer

print(solution(['SL', 'LR'])) # [16]