[파이썬] 프로그래머스 : 빛의 경로 사이클 (Lv.2)

[파이썬] 프로그래머스 : 빛의 경로 사이클 (Lv.2)

 

프로그래머스

 

---

풀이

방향성 생각

학부연구생 민상처럼 한 방향에 좌표마다 4가지 방향을 visit으로 처리한다.

DFS로 탐색. 사이클 재방문하면 탈출, 아니면 재귀

한 좌표에 같은 방향으로 입력이 들어오면 사이클 발생(재방문)이므로 탈출한다.

전체코드

import sys
sys.setrecursionlimit(10**8)

def solution(grid):
    h,w = len(grid),len(grid[0])
    visit = [[[False]*4 for _ in range(w)] for _ in range(h)]
    step = [(1,0),(0,1),(-1,0),(0,-1)]

    def dfs(x, y, dire, cnt):
        visit[y][x][dire] = True
        dx,dy = step[dire]
        nx,ny = (x+dx)%w,(y+dy)%h

        if grid[ny][nx] == 'S':
            ndire = dire
        elif grid[ny][nx] == 'L':
            ndire = (dire-1)%4
        elif grid[ny][nx] == 'R':
            ndire = (dire+1)%4

        if not visit[ny][nx][ndire]:
            return dfs(nx,ny,ndire,cnt+1) 
        else:
            return cnt

    answer = []
    for i in range(h):
        for j in range(w):
            for k in range(4):
                if not visit[i][j][k]:
                    answer.append(dfs(j,i,k,1))
    answer.sort()
    return answer

코멘트

마법사 상어와 복제처럼 방향 시계, 반시계 전환 필요할 때 상하좌우가 아니라, 상 우 하 좌 이런식으로 정의하는게 편함.