[프로그래머스] Lv2 - 빛의 경로 사이클 (파이썬)

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

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

 

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def solution(grid):
    global answer, visited
    global N, M
    answer = []
    N = len(grid)
    M = len(grid[0])
    visited = [[[False]*4 for _ in range(M)] for _ in range(N)]

    for i in range(N):
        for j in range(M):
            for k in range(4):
                if not visited[i][j][k]:
                    light(i, j, k, grid)

    return sorted(answer)


def light(x, y, k, grid):
    global answer
    nx, ny, dir = x, y, k
    num = 0
    visited[x][y][k] = True
    while True:
        if grid[nx][ny] == 'R':
            dir = (dir+1) % 4
        elif grid[nx][ny] == 'L':
            dir = (dir-1) % 4

        nx = (nx + dx[dir]) % N
        ny = (ny + dy[dir]) % M
        num += 1

        if visited[nx][ny][dir]:
            if nx == x and ny == y and dir == k:
                answer.append(num)
                return

        visited[nx][ny][dir] = True

 

DFS
1. 방문 여부를 각 지점, 방향으로 3차원 배열로 선언
2. 모든 지점에서 빛이 네 방향으로 퍼진다. (각 지점마다 모든 방향을 검사)
3. light : 빛이 이동하는 함수
    - 해당 지점의 방향을 방문 처리하면서 이동한 거리 num에 기억
    - 지점과 방향이 방문됐다면, 처음 시작한 정보와 같은지 비교 (사이클), 같으면 answer에 append
4. 오름차순 정렬해서 반환

 

조금 헤맸던 문제

팁은 좌표가 0부터 시작을 하기 때문에 범위를 넘어섰을 경우 해당 거리로 나머지 연산을 실행하면 반대편으로 간다.

문제에 오름차순 정렬을 해서 반환하라고 적혀있는데 그걸 안 봐서 사서 고생을 했다.

앞으로 문제를 정독하고 풀어야겠다.