Level 2 빛의 경로 사이클 Python 3

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

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

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_빛의경로사이클.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = []

def shoot_light(x, y, d, grid, visit, ans_visit):
    length = 0
    
    while True:
        nd = d
        if grid[y][x] == 'L':
            nd = (d-1+4)%4
        elif grid[y][x] == 'R':
            nd = (d+1+4)%4
            
        nx = x + dx[nd]
        if nx < 0: nx += len(grid[0])
        elif nx >= len(grid[0]): nx -= len(grid[0])
        
        ny = y + dy[nd]
        if ny < 0: ny += len(grid)
        elif ny >= len(grid): ny -= len(grid)
        
        if visit[nd][ny][nx] > 0 and length > 0:
            if visit[d][y][x] == 0:
                answer.append(length)
                visit[d][y][x] = length
            return
        
        length += 1
        visit[nd][ny][nx] = length
        x = nx
        y = ny
        d = nd
    
def solution(grid):
    ans_visit = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]
    visit = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]

    for d in range(4):
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if visit[d][y][x] > 0: continue
                shoot_light(x, y, d, grid, visit, ans_visit)
    answer.sort()
    return answer

---

풀이 과정

풀이 시간 1시간 30분

어려운 문제는 아니지만 문제를 한번에 명확하게 이해하지 못해서 헤맸다.

무조건 빛은 (0, 0)의 상, 하, 좌, 우 방향을 시작으로 쏘는 줄 알았는데, grid의 모든 칸에서 상, 하, 좌, 우로 시작할 수 있다.

주의 할 점은 3차원 visit과 ans_visit 배열을 생성해서 visit[방향][y좌표][x좌표]에 빛이 순환하는 길이를 담아주어야 한다.

그리고 ans_visit에는 사이클의 시작 및 종료 좌표에 최종 사이클 길이를 담아준다.

ans_visit[방향][y좌표][x좌표]에 이전에 생성된 사이클 값이 있다면 중복된 사이클이기 때문에 answer에 length를 추가하지 않고, 처음 생성된 사이클이라면 answer에 length를 추가해준다.

#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = []

def shoot_light(x, y, d, grid, visit, ans_visit):
	#빛의 길이 초기화
    length = 0
    
    while True:
    	#변화된 방향 구하기
        nd = d
        if grid[y][x] == 'L':
            nd = (d-1+4)%4
        elif grid[y][x] == 'R':
            nd = (d+1+4)%4
        
        #이동할 다음 좌표 구하기
        nx = x + dx[nd]
        if nx < 0: nx += len(grid[0])
        elif nx >= len(grid[0]): nx -= len(grid[0])
        
        ny = y + dy[nd]
        if ny < 0: ny += len(grid)
        elif ny >= len(grid): ny -= len(grid)
        
        #이전에 순환한 좌표인 경우, 사이클이 형성됨
        if visit[nd][ny][nx] > 0 and length > 0:
        
        	#첫 순환인 경우, answer에 빛의 길이를 담아주고, ans_visit에 최종 사이클 길이를 담아준다
            if ans_visit[d][y][x] == 0:
                answer.append(length)
                ans_visit[d][y][x] = length
                
            #탐색을 종료한다
            return
        
        #빛의 길이를 1 증가하고, 빛이 지나간 경로를 방문처리 한다
        length += 1
        visit[nd][ny][nx] = length
        x = nx
        y = ny
        d = nd
    
def solution(grid):
	#사이클이 생성된 최종 좌표와 마지막 방향에 사이클 길이를 담아주는 배열 
    ans_visit = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]
    
    #모든 좌표와 방향에서 생성된 사이클 길이를 담아주는 배열
    visit = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]

	#모든 좌표와 모든 방향에 대하여 처음 빛을 쏜다
    for d in range(4):
        for y in range(len(grid)):
            for x in range(len(grid[0])):
            	#이전에 빛이 순환한 곳이라면 더이상 탐색하지 않는다
                if visit[d][y][x] > 0: continue
                
                #첫 시작점이라면 빛을 순환시킨다
                shoot_light(x, y, d, grid, visit, ans_visit)
    answer.sort()
    return answer
    
#시간복잡도 = O(n log n), 공간복잡도 = O(n)