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

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

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

 

각각의 위치에 대해서 모든 방향으로 방문했는지 체크하면서, 이동할 때에 규칙을 잘 설정해야 한다.

마지막에 오름차순으로 정렬하는걸 못 봐서 한참 헤맸다.

 

나의 풀이

from collections import deque
def solution(grid):
    answer =[]
    len_x, len_y = len(grid),len(grid[0])
    visited = [[[0]*4 for _ in range(len_y)] for _ in range(len_x)]
    # D U L R
    move_dict = {0:(1,0),1:(-1,0),2:(0,-1),3:(0,1)}
    next_move_dict = {'S':{0:0,1:1,2:2,3:3},'L':{0:3,1:2,2:0,3:1},'R':{0:2,1:3,2:1,3:0}}
    for i in range(len_x):
        for j in range(len_y):
            while 0 in visited[i][j]:
                queue = deque()
                # do something
                idx = visited[i][j].index(0)
                # serach
                queue.append((i,j,idx,1,[i,j,idx]))
                visited[i][j][idx] = 1 # 해당 경로 방문처리
                while queue:
                    x, y, move, counting, first_move = queue.popleft()
                    df_x, df_y = move_dict[move]
                    x, y = x + df_x, y + df_y
                    if x == len_x:
                        x = 0
                    elif x < 0:
                        x = len_x-1
                    if y == len_y:
                        y = 0
                    elif y < 0:
                        y = len_y-1
                    next_idx = next_move_dict[grid[x][y]][move]
                    if [x,y,next_idx] == first_move:
                        answer.append(counting)
                    else:
                        visited[x][y][next_idx] = 1
                        queue.append((x,y,next_idx,counting+1,first_move))
    return sorted(answer)

 

dfs 풀이 (나중에 참고)

import sys

sys.setrecursionlimit(10 ** 6)

def out(x, y, d, grid, dic):
    nx = x + dic[d][0]
    ny = y + dic[d][1]
    
    if nx >= len(grid):
        nx = 0
    elif nx < 0:
        nx = len(grid)-1
    
    if ny >= len(grid[0]):
        ny = 0
    elif ny < 0:
        ny = len(grid[0])-1
        
    return nx, ny
    

def dfs(state, org, route, grid):
    dic = {0:[-1, 0], 1:[0, 1], 2:[1, 0], 3:[0, -1]}
    x = state[0]
    y = state[1]
    d = state[2]
    visited[d][x][y] = 1
    
    nx, ny = out(x, y, d, grid, dic)
    value = grid[nx][ny]
    
    if value == 'R':
        d = (d + 5) % 4
        
    elif value == 'L':
        d = (d + 7) % 4
    
    if org[0] == nx and org[1] == ny and org[2] == d:
        answer.append(route)
        return
    
    if not visited[d][nx][ny]:
        dfs([nx, ny, d], org, route+1, grid)
        
def solution(grid):
    global answer, visited
    
    answer = []
    visited = [[[0]*len(grid[0]) for _ in range(len(grid))] for _ in range(4)]
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for d in range(4):
                dfs([i, j, d], [i, j, d], 1, grid)
                    
    return sorted(answer)