Computer Vision 대학원생 기록지

코딩테스트 연습 - 빛의 경로 사이클 | 프로그래머스 (programmers.co.kr)

REVIEW

• graph와 경로의 길이를 보고 bfs 문제인가 싶지만 여러 대안 경로 중에서 나은 것을 선택하는 것이 아니라, 각 node 마다 주어진 S, R, L 명령구에 따라 경로가 정해지기 때문에 bfs로 풀 필요가 없다. 
• 같은 노드여도 어느 방향에서 들어왔는지에 따라 구분되기 때문에 visited를 만들 때 3차원으로 만들어 방향 정보를 추가하였다. 따라서 node b에서 북쪽으로 나아갔다면, 다음 번에 node b에서 남쪽으로 나아갈 때는 visited 여부가 False가 된다.
• 방문한 적 없는 노드에서 시작하여 방문한 적이 있는 노드에 방문하게 된 경우 사이클이 발생한 것이다.
• 이전 사이클에서 이미 방문한 노드가 이번 사이클에서 방문한 것으로 오인되는 것이 아닌가라고 생각할 수 있지만, 동일한 경로가 아닌 이상 동일한 노드에 대하여 동일한 방향으로 방문하는 일은 없다. (각 노드마다 변하지 않는 명령구가 있기 때문이다.) 
• 또한 이러한 특성 덕분에 중복되는 경로를 answer에 추가하는 경우를 피할 수 있었다.

# direction: north=0, east=1, south=2, west=3
from collections import deque


def direction(oper, d):
    
    if oper == 'L': 
        d = (d-1)%4
    elif oper == 'R': 
        d = (d+1)%4
    return d
    
def bfs(x, y, d, width, height, graph, grid):
    
    count = 0
    start = [x, y, d]
    while True:
        # add current node to Visited
        if graph[x][y][d]:
            ans = count
            count = 0
            return ans
        graph[x][y][d] = 1
        count += 1
        
        # Move
        # to North
        if d == 0:
            x = (x+1)%height
        # to East
        elif d == 1:
            y = (y+1)%width
        # to South
        elif d ==2:
            x = (x-1)%height
        # to West
        else:
            y = (y-1)%width
        
        # change direction
        d = direction(grid[x][y], d)
        
def solution(grid):
    graph = [[[0, 0, 0, 0] for _ in range(len(grid[0]))] for _ in range(len(grid))]
    answer = []
    
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if graph[i][j][k] != 1:
                    num = bfs(i, j, k, len(grid[0]), len(grid), graph, grid)
                    answer.append(num)
    answer.sort()
    return answer