유의할 점

1. BFS 문제다.
2. 3차원 배열을 이용해야 한다.
3. 재귀를 이용하면 StackOverflow 가 난다.

def solution(grid):
    row = len(grid)
    col = len(grid[0])

    def move(r, c, d):
        
        if d == 0:
            r -= 1
        elif d == 1:
            c -= 1
        elif d == 2:
            r += 1
        else:
            c += 1
        if r < 0 or r >= row:
            r %= row
        if c < 0 or c >= col:
            c %= col
        
        return r,c
    
    def rotate(r, c, d):
        if grid[r][c] == 'S':
            return d
        elif grid[r][c] == 'L':
            return (d+1)%4
        else:
            return (d-1)%4
        
    
    
    answer = []
    # visited[r][c][d] : 3차원 배열 - (r, c) 에서 d 방향으로 나간 적이 있는지 기록
    
    dir = ["up", "left", "down", "right"]
    
    
    visited = [[[False for i in range(4)] for j in range(col)] for k in range(row)]
    # print(visited)
    
    for i in range(row):
        for j in range(col):
            for k in range(4):
                r, c, d = i, j, k
                cnt = 0
                while not visited[r][c][d]:
                    # 한 노드에서 같은 방향으로 나간 것은 곧 같은 사이클이라는 것을 의미하므로 중복 제거
                    visited[r][c][d] = True
                    r, c = move(r, c, d)
                    d = rotate(r, c, d)
                    cnt += 1
                    
                if cnt != 0:
                    answer.append(cnt)
    answer.sort()
    
    return answer

답은 이건데... 처음에 answer.sort() 를 answer.append(cnt) 바로 아래에 써서 테스트케이스 9, 10, 11 이 계속 시간초과가 떴다. 당연하지... append 할 때마다 정렬을 해서 결과적으로 시간복잡도가 n배가 됐는데... 저 문제로 거의 2시간 동안 고민하다 해결했을 때 너무 허무했다.