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

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

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

특별한 알고리즘이 쓰이는 문제는 아니고, 직접 탐색을 하는 문제입니다. 

 

우선 문제부터 간단하게 요약해보면, 

다음과 같은 grid에 빛을 쏩니다. 이때 각각에는 S, L, R이 적혀 있고, 빛을 직진, 왼쪽, 오른쪽으로 각각 발사시킵니다. 이때, 각각의 cycle의 길이를 오름차순으로 return하는 것이 문제입니다. 조금더 자세한 내용은 위의 링크를 직접 읽어보시는 것이 정확합니다. 

 

즉 solution(grid) 에 

grid : 현재 grid 의 2D 배열이

이 input으로 주어질 때, 

 

각각의 cycle의 길이를 구하고, 그 길이를 오름차순으로 array에 담아 return해야 합니다. 

 

아이디어, 정답과 함께, 주의해야하는 점들에 대해 review해보겠습니다. 

 

<Solution>

우선 이 문제를 가장 처음 보았을 때, 곰곰히 생각해본점은 다음과 같은 경우입니다. 

다음과 같이 어떠한 사이클이 다른 사이클을 포함 시킬 수 있는가? 라는 질문을 먼저 생각해 보았습니다. 하지만 각각 grid안의 node는 빛을 쏘는 방향이 정해져있기에, 중간에 부분적인 path로 빠질 수가 없습니다. 그림으로 조금 더 설명해보면, 

위 그림처럼 무조건 같은 방향으로 같은 node에 빛이 들어와야 경로 탐색이 끝날 수 있습니다. 이것을 이용해 완전 탐색을 진행하면 문제를 풀 수 있습니다. 

 

하지만 이 완전탐색 과정을 구현하는데에는 일부 주의해야하는 점들이 있었습니다. 

1. Recursive한 함수를 구성하면, 일부 testcase에서 recursion depth가 너무 깊어져서 runtime error가 발생하는 것을 알 수 있었음 2. 매번 어떤 노드부터 출발해야하는지를 탐색해서 정해주면, timeout이 발생함

각각 코드로 문제점과 해결방법을 보도록 합시다.

 

1번문제에 관한 코드

<잘못된 코드>

    def move(path_list, start_node, start_direction, c):
        # print(f'move input :\n{start_node, start_direction, c}')
        if path_list[start_node][start_direction] == 0:
            return c
        path_list[start_node][start_direction] = 0
        c += 1
        # calculate next_node
        next_node = (((start_node[0]+direct_[start_direction][0]))%row_c, (start_node[1]+direct_[start_direction][1])%column_c)
        
        # calculate next_direction
        # get next node LRS info
        d = grid_list[next_node[0]][next_node[1]]
        if d == 'L':
            next_direction = (start_direction-1)%4
        elif d == 'R':
            next_direction = (start_direction+1)%4
        else: # 'S'
            next_direction = start_direction
        return move(path_list, next_node, next_direction, c)

출발지점과 출발 direction을 넣어주면, 경로 탐색을 모두 한 이후에 탐색횟수를 return해주는 함수입니다. 다음과 같이 recursive 하게 함수를 구성한 경우, 프로그래머스에서 일부 testcase에서 runtime error가 나옴을 알 수 있었습니다. 

 

<올바른 코드>

    def move(path_list, start_node, start_direction):
        c = 0
        while(path_list[start_node][start_direction] != 0):
            path_list[start_node][start_direction] = 0
            c+=1 
            # calculate next_node
            next_node = (((start_node[0]+direct_[start_direction][0]))%row_c, (start_node[1]+direct_[start_direction][1])%column_c)
            # calculate next_direction
            # get next node LRS info
            d = grid_list[next_node[0]][next_node[1]]
            if d == 'L':
                next_direction = (start_direction-1)%4
            elif d == 'R':
                next_direction = (start_direction+1)%4
            else: # 'S'
                next_direction = start_direction
            start_node = next_node
            start_direction = next_direction
        return c

다음과 같이 while 문을 통해 재귀함수의 호출 없이 코드를 구성한 경우, 에러가 해결되는 것을 알 수 있었습니다. 

 

2번 문제에 관한 코드

<잘못된 코드>

    counter = 4*row_c*column_c
    answer_list = []
    while counter:
        #find first point to search
        b_flag = 0
        for key in path_list.keys():
            for direction, e in enumerate(path_list[key]):
                if e == 1:
                    start_node = key
                    start_direction = direction
                    b_flag = 1
                    break
            if b_flag == 1:
                break
        tmp = move(path_list, start_node, start_direction)
        answer_list.append(tmp)
        counter -= tmp

다음과 같이 매번 선형 탐색을 해서, 아직 탐색하지 않은 경우에 출발지로 지정해주었습니다. 이렇게 하면, 매번 선형 탐색을 해야하므로 굉장히 비효율적이여서 timeout이 발생합니다. 

 

<올바른 코드>

    answer_list = []
    for r in range(row_c):
        for c in range(column_c):
            for _ in range(4):
                if path_list[(r,c)][_] == 1:
                    tmp = move(path_list, (r,c), _)
                    answer_list.append(tmp)

다음과 같이 한번씩만 조회하면서 방문했는지 안했는지만 체크하는 방식이 좀더 시간을 단축시켜줍니다. 

 

실제 전체 코드는 아래와 같습니다. 

from collections import defaultdict
direct_ = [(-1,0), (0,1), (1,0), (0,-1)] # up right down left (row,column)

def solution(grid):
    
    def move(path_list, start_node, start_direction):
        c = 0
        while(path_list[start_node][start_direction] != 0):
            path_list[start_node][start_direction] = 0
            c+=1 
            # calculate next_node
            next_node = (((start_node[0]+direct_[start_direction][0]))%row_c, (start_node[1]+direct_[start_direction][1])%column_c)
            # calculate next_direction
            # get next node LRS info
            d = grid_list[next_node[0]][next_node[1]]
            if d == 'L':
                next_direction = (start_direction-1)%4
            elif d == 'R':
                next_direction = (start_direction+1)%4
            else: # 'S'
                next_direction = start_direction
            
            start_node = next_node
            start_direction = next_direction
        return c

    grid_list = list(map(list, grid))
    path_list = defaultdict(list)

    row_c = len(grid_list)
    column_c = len(grid_list[0])
    for row in range(row_c):
        for column in range(column_c):
            path_list[(row,column)] = [1,1,1,1] # up right down left 

    path_list = dict(path_list)
    answer_list = []
    for r in range(row_c):
        for c in range(column_c):
            for _ in range(4):
                if path_list[(r,c)][_] == 1:
                    tmp = move(path_list, (r,c), _)
                    answer_list.append(tmp)
        
    return sorted(answer_list)