프로그래머스 빛의 경로 사이클 (python, 파이썬)

• 문제

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

---

• 제한사항
  • 1 ≤ grid의 길이 ≤ 500
    • 1 ≤ grid의 각 문자열의 길이 ≤ 500
    • grid의 모든 문자열의 길이는 서로 같습니다.
    • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

---

• 입/출력

grid	result
["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

---

• 코드

import sys

sys.setrecursionlimit(10 ** 6)

def out(x, y, d, grid, dic):
    nx = x + dic[d][0]
    ny = y + dic[d][1]
    
    if nx >= len(grid):
        nx = 0
    elif nx < 0:
        nx = len(grid)-1
    
    if ny >= len(grid[0]):
        ny = 0
    elif ny < 0:
        ny = len(grid[0])-1
        
    return nx, ny
    

def dfs(state, org, route, grid):
    dic = {0:[-1, 0], 1:[0, 1], 2:[1, 0], 3:[0, -1]}
    x = state[0]
    y = state[1]
    d = state[2]
    visited[d][x][y] = 1
    
    nx, ny = out(x, y, d, grid, dic)
    value = grid[nx][ny]
    
    if value == 'R':
        d = (d + 5) % 4
        
    elif value == 'L':
        d = (d + 7) % 4
    
    if org[0] == nx and org[1] == ny and org[2] == d:
        answer.append(route)
        return
    
    if not visited[d][nx][ny]:
        dfs([nx, ny, d], org, route+1, grid)
        
def solution(grid):
    global answer, visited
    
    answer = []
    visited = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for d in range(4):
                dfs([i, j, d], [i, j, d], 1, grid)
                    
    return sorted(answer)

dfs로 빛이 갈수 있는 것을 탐색해준다.

 

단, 모든 경우의 수를 진행하게되면 시간초과가 발생하기 때문에 방문한적이 없는곳만 진행을 해주어야한다.

(방문한적이 있는 곳은 어자피 들어오면 같은 싸이클이 이루어지기떄문에 필요x)

 

다른 문제와는 조금 다른것이 빛의 진행방향이 어디서 들어오냐에 따라서 달라지는 것이다.

visited를 n(세로의길이) x m(가로의길이) x d(방향)으로 만들어준다,

해당 노드의 방문했다고 종료하는것이 아닌 해당노드에서 방향까지 고려해서 방문한적이 있다면 종료

 

L, R이 들어오면 방향이 바뀌는것은 규칙이 있기 때문에 위에 코드를 통해서 확인하면됩니다!

---

• 출처

https://programmers.co.kr/learn/courses/30/lessons/86052?language=python3