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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/86052

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

 

구현, 시뮬레이션 문제이다.

각 칸에 명령에 따라 진행방향을 정하고 다음 칸으로 이동한다. 이때 이동하다가 처음 시작점, 시작방향이 똑같은 점으로 오면 한 사이클이 생성된 것이다. 이때 사이클의 길이를 구하는 문제이다.

 

나는 각 점에서 나가는 방향을 기준으로 사이클을 판별했다. 만약 같은 칸에 다른 방향으로 빛이 나아가게 된다면 사이클이 아니다. 즉 같은 칸 같은 방향으로 나가는게 또 들어온다면 사이클이 형성 된 것이다.

그래서 3차원 배열로 사용 했다. [x][y][나가는 방향]

 

시작점에서 4방향으로 빛을 쏴보면서 시작한다.

사이클이 형성될 때 까지 반복문을 돈다.

 

일단 방향을 이동시키고 다음 해당 칸에 따라 방향을 변경한다.

이때 바뀐 점과 방향으로 방문 체크를 수행한다. 만약 방문한 칸이고 시작점과 방향이 같다면 사이클이 형성 된 것이므로 이동 횟수를 반환하자

그렇지 않고 다른 점인데 이미 방문한 점이라면 사이클이 정상적으로 형성된것이 아니기 때문에 0을 반환하자.

주의할 점이라면 이동 시 범위를 벗어나면 반대편 점으로 이동한다. 그래서 모듈러 연산으로 순환되게 하자.

 

이제 이 사이클 값들을 배열에 저장하자.

 

마지막에 해당 값들을 오름차순으로 정렬해야한다.

나는 멍청하게 정렬안해서 계속 틀렸었다.

 

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 = []
    visited = [[[False]*4 for _ in range(m)] for _ in range(n)]
    for sx in range(n):
        for sy in range(m):
            for d in range(4):
                if not visited[sx][sy][d]:
                    rst = simul(sx,sy,d,grid)
                    if rst != 0:
                        answer.append(rst)
    answer.sort()
    return answer

def simul(sx,sy,sd,grid):
    global visited
    x,y,d=sx,sy,sd
    cnt = 0
    visited[sx][sy][sd] = True
    while True:
        x = (x + dx[d]) % n
        y = (y + dy[d]) % m
        cnt += 1

        if grid[x][y] == 'R':
            d = (d+1)%4
        elif grid[x][y] == 'L':
            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] = True