프로그래머스 빛의 경로 사이클(Python)

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

프로그래머스

이번 레벨 2는 저에게 너무 어려웠습니다... 어떻게 시작해야 할지 조차 감을 잡지 못해서 한참을 멍 때렸던 문제였습니다 ㅋㅋㅋㅋ

한 50분~1시간 생각해보다 도저히 모르겠어서 결국 아래의 사이트에서 배웠습니다.

https://westmino.tistory.com/86

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

다른 사람의 코드

이 분은 DFS 느낌으로 문제를 풀어나갔습니다. 각 cell 마다 다음으로 뻗어나갈 방향 별로 또 나눠서 각각 방문했던 방식인지 판단했습니다. grid가 ["SL", "LL"]인 경우, 그림으로 표현하자면 이런 느낌입니다.

grid별 방문 여부 표시 방법

셀에 도착할 때 다음 뻗어갈 방향을 결정하는데 dx, dy 리스트를 이용했습니다. 셀이 "L"이냐 "R"이냐에 따라 dx, dy의 값을 이용해 다음 방문할 셀의 위치를 계산했습니다.

그리고 원래 코드에서는 visited를 global 변수로 선언하고 풀으셨는데 저는 개인적으로 global을 싫어하는 사람인지라... global을 없애고 모두 함수의 인자로 주는 방법으로 바꿨습니다. 그렇게 풀은 결과가 아래와 같습니다.

def simulation(_x, _y, _d, _grid, _visited):
    next_x, next_y, next_d = _x, _y, _d
    cnt = 0
    r, c = len(_grid), len(_grid[0])
    # 아래, 왼쪽, 위, 오른쪽 순서
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    direction_ways = len(dx)
    _visited[_x][_y][_d] = True
    
    while True:
        next_x = (next_x + dx[next_d]) % r
        next_y = (next_y + dy[next_d]) % c
        cnt += 1
        
        if _grid[next_x][next_y] == "L":
            next_d = (next_d - 1) % direction_ways
        elif _grid[next_x][next_y] == "R":
            next_d = (next_d + 1) % direction_ways
            
        if _visited[next_x][next_y][next_d]:
            return cnt if (next_x, next_y, next_d) == (_x, _y, _d) else 0
        
        _visited[next_x][next_y][next_d] = True

def solution(grid):
    answer = []
    r, c = len(grid), len(grid[0])
    visited = [[[False] * 4 for _ in range(c)] for _ in range(r)]
    
    for start_x in range(r):
        for start_y in range(c):
            for d in range(4):
                if not visited[start_x][start_y][d]:
                    cycle_len = simulation(start_x, start_y, d, grid, visited)
                    if cycle_len:
                        answer.append(cycle_len)
    answer.sort()
    return answer

프로그래머스 채점 서버에서 돌려본 결과, 최대 634.64ms, 39.7MB의 자원을 소모했습니다.

 

그동안 본 레벨 2 문제들 중에 제일 어려웠던 것 같습니다... 그리고 DFS, BFS 풀이법이 생각보다 많이 사용된다는 것을 느꼈습니다!