[Python 문제 풀이] 프로그래머스 '빛의 경로 사이클'

Programmers Lv.2 '빛의 경로 사이클' 파이썬 코드 및 풀이

 

 

 

딱 봐도 어려워 보이는 문제이다. 차근차근 제약조건을 뽑아내서 접근 방법을 좁혀보자.

 

시간복잡도

 

grid는 최대길이 500인 것이 최대 500개 모여있는 것이다.

표현하자면 최대 500x500 크기의 행렬이 될 것이다.

모든 지점을 탐색한다고 할 때 N은 최대 250,000이다.

시간복잡도 O(N) 혹은 O(NlogN)까지도 가능할 것 같다.

 

자료구조

 

사이클의 갯수와 경로의 길이를 알기 위해 우리는 프로그램적으로 빛을 이동시켜야 하고 이 경로를 기록해야 한다.

경로를 만들면서 몇 개의 지점을 지났는지, 한번 사이클이 완성되면 또 지나지 않은 경로는 어디에 있는지 알아야 한다.

다행히도 빛의 경로는 들어오는 것과 나가는 것이 일대일대응을 이루기 때문에 서로 다른 빛의 경로 사이클은 절대 겹치지 않는다.

즉 들어오는 방향이 정해지면 나가는 방향은 저절로 정해진다.

들어오거나 나가거나 둘 중 하나만 정해서 4개만 기록하자.

NxM 2차원 배열에 추가로 한 차원을 더 해 3차원 배열을 만들고 상하좌우 네 개의 방향의 길을 지났는지를 가리키는 네 개의 원소를 기록하면 되겠다.

 

의사코드

지나지 않은 경로를 찾는다.

해당 지점에서 빛을 쏜다.

다음 방향을 확인하면서 반복한다.

경로의 길이와 경로를 지났음을 기록한다.

이미 지나온 경로가 나타나면 사이클이 완성되므로 반복 종료

다시 지나지 않은 경로를 찾는다.

 

구현

def solution(grid):
    answer = []
    rows, cols = len(grid), len(grid[0])
    gone = [[[False for _ in range(4)] for _ in range(cols)] for _ in range(rows)]
    
    # go => [Up,Right,Down,Left]
    go = [[-1,0], [0,1], [1,0], [0,-1]]
    
    # shoot light and get cycle
    def travel(r,c,d) :
        count = 0
        while True :
            gone[r][c][d] = True
            count += 1
            
            #fetch
            dr,dc = go[d]
            rr,cc = r + dr, c + dc
            
            # fix value over boundary
            r = (rr + rows) % rows
            c = (cc + cols) % cols
            
            #get new direction
            if grid[r][c] == 'L' :
                d = (d + 3) % 4
            elif grid[r][c] == 'R' :
                d = (d + 1) % 4
                
            if gone[r][c][d] :
                break
        return count
    
    #search all nodes
    for i in range(rows) : 
        for j in range(cols) : 
            for k in range(4) :
                if not gone[i][j][k] :
                    r,c,d = i,j,k
                    answer.append(travel(r,c,d))
                    
    return sorted(answer)

 

각 방향의 경로를 지났는지를 나타내는 데이터에서 원소의 순서를 상,우,하,좌로 하면 방향전환 계산이 쉽다.

비슷한 방법으로 경계 바깥쪽으로 쏘아진 빛에 대해서도 계산할 수 있다.

한편, 사이클을 만드는 것은 비교적 쉬우나, 이 문제의 핵심은 지나지 않은 경로를 다시 찾는 것이다.

3차원 배열의 원소의 개수는 최대 500x500x4 = 1,000,000이다.

놀랍게도 N이 정확히 100만이 되면서 시간복잡도 O(N)만에 풀어야하는 문제가 된다.

작은 길이의 사이클이 무수히 존재하게 되면 지나지 않은 경로를 찾는 과정을 아주 많이 수행하게 되며 시간초과가 발생할 수 있다.

나는 지나온 경로를 찾는 수행 안에서 사이클을 만들도록 하여, 적어도 한 번 확인 했던 경로는 반드시 지났을 것이기 때문에 다시 확인하지 않는 방법으로 시간을 줄였다.

이 보다 더 확실하고 효율적인 방법이 있을 것 같다. 여러분이 찾아서 알려주면 좋겠다.