[Programmers] 빛의 경로 사이클 (Python 풀이)

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

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

---

["SR","LR"]에서의 사이클

이 문제는 좌표에서의 빛의 이동 방향에 따라 어떤 사이클이 존재하는지, 또 해당 사이클의 길이는 어떻게 되는지 조사하는 문제입니다. ㅁ

각 좌표에 대해 4방향에서 전송되는 값에 대하여 탐색을 하며 빛을 이동 시킵니다. 만약 중복이 되는 방향이 나타나는 경우 탐색을 정지해야합니다. 예를 들어 좌표 A에 방향 d가 중복되서 발견되는 경우 이는 순환 사이클이기 때문입니다.

소스 코드

#     ↓  ←   ↑  →
dy = (1, 0, -1, 0)
dx = (0, -1, 0, 1)
 
def solution(grid):
    answer = []
 
    ly, lx = len(grid), len(grid[0])
 
    # 4방향 방문 기록 리스트 : y*x*4
    visited = [[[False] * 4 for _ in range(lx)] for _ in range(ly)]
 
    # 모든 좌표에 대하여 탐색
    for y in range(ly):
        for x in range(lx):
 
            # (y, x) 좌표에 대해 4방향 탐색
            for d in range(4):
                # 해당 좌표-방향 이 기존에 사용된 경우
                if visited[y][x][d]:
                    continue
                
                # 사용되지 않은 좌표-방향인 경우
                count = 0
                ny, nx = y, x
                # 빛을 이동 시켜가며 탐색
                while not visited[ny][nx][d]:
                    visited[ny][nx][d] = True
                    count += 1
                    if grid[ny][nx] == "S": # S의 경우 방향 변경 X
                        pass
                    elif grid[ny][nx] == "L": # L의 경우 반시계방향
                        d = (d - 1) % 4
                    elif grid[ny][nx] == "R": # R의 경우 시계방향
                        d = (d + 1) % 4
                    
                    # 좌표의 길이로 %연산을 하여 격자를 벗어난 경우에도 자리를 찾아가도록함.
                    ny = (ny + dy[d]) % ly 
                    nx = (nx + dx[d]) % lx
 
                answer.append(count)
    answer = sorted(answer) # 오름차순 정렬
    return answer

 

11번 라인 : 각 좌표에 대해 4방향에 대한 방문 기록용 Boolean 배열 선언

25~39번 라인 : 좌표의 값에 따라 방향을 바꿔가며 사이클 탐색, 루프가 돌때마다 길이를 1씩 증가시킵니다. 만약 이동한 좌표-방향이 이미 사용된 좌표-방향이라면 이 다음 루프 부터는 이미 순환한 경로로 순환하기 때문에 더이상 탐색하지 않고 멈춥니다.

32~34번 라인 : 좌표의 값에 따라 방향값(d)을 바꿉니다.

38~39번 라인 : 현재 가리키고 있는 방향(d)으로 빛을 이동시킵니다. 격자 밖으로 나가는 경우도 처리하기 위해여 행의 길이(혹은 열의 길이)로 % 연산을 수행합니다.

42번 라인 : 저장된 사이클 길이들을 오름차순으로 정렬한 후 반환합니다.

 

실행 결과