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

---

문제설명

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

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

사고과정

• DFS 탐색으로 사이클을 판별하는 문제라는 것을 인지는 했지만 어떻게 풀어나가야 할지 도저히 감이 오지 않았다.. 그래서 문제의 질문하기에서 어떤 분이 설명해주신 글을 보고 방문용 테이블을 3차원 배열로 정의해야 한다는 것을 알았다..보통은 사이클을 판별하기 위해서는 도착한 방향에 상관없이 그냥 그 노드에만 다시 돌아오면 사이클이 있다고 판별하면 되었지만 이번 문제는 '방향'까지 고려해야 하는 문제였다.. 도저히 풀 엄두가 안나서 구글링해서 다른 분의 풀이를 따라치면서 풀이를 이해해 나갔다..
• 손도 못댄 문제는 오랜만이었다.. 아직 갈 길이 멀드아.. 다른분의 풀이는 여기를 참고하자.
• 몇 일간 계속 이 문제를 반복해서 풀어봐야 겠다. 완벽히 이해가 될 때까지!

풀이(스스로 못 푼 풀이)

# 빛을 쏘는 방향 좌<--(왼쪽)-- 상 --(오른쪽)-->우  방향으로 되도록 설정
# 얘는 하,좌,상,우 로 설정
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def solution(grid):
    global visited, n, m
    n = len(grid)
    m = len(grid[0])
    answer = []
    # 노드 위치, 방향 기록할 3차원 방문 테이블 정의
    visited = [[[0] * 4 for _ in range(m)] for _ in range(n)]
    for sx in range(n):
        for sy in range(m):
            for sd in range(4):
                if not visited[sx][sy][sd]:
                    res = simul(sx, sy, sd, grid)
                    if res != 0:
                        answer.append(res)

    answer.sort()
    return answer


def simul(sx, sy, sd, grid):
    global visited
    # 시작점과 시작방향
    x, y, d = sx, sy, sd
    cnt = 0  # 사이클 길이
    visited[x][y][d] = 1 # 시작점, 시작방향 방문체크
    while True:
        x = (x + dx[d]) % n  # 범위 벗어나는 것은 반대편으로 설정하기 위해 % 연산 사용
        y = (y + dy[d]) % m 
        cnt += 1
        
        if grid[x][y] == 'L': # 방향을 왼쪽으로 변경
            d = (d - 1) % 4
        elif grid[x][y] == 'R': # 방향을 오른쪽으로 변경
            d = (d + 1) % 4
        # 만약 지금 탐색하는 노드가 방문한 적이 있다면!
        if visited[x][y][d]:
            if (x, y, d) == (sx, sy, sd):  # 시작방향도 이미 방문한 곳이라면 사이클!
                return cnt
            else:
                return 0
        visited[x][y][d] = 1 # 현재 탐색하는 노드 방문처리