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

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

grid에 있는 각 정점마다 동서남북 4방향으로 접근했을 때, 생기는 사이클의 길이들을 구하는 문제

접근방법: 각 정점마다 4가지 방향으로 탐색시작
visited를 통해 방문 여부를 확인하여 사이클을 찾음
S, R , L별로 방향 회전을 적절히 해주면 쉽게 풀 수 있음

초기코드

from collections import deque

def trans(ni,nj, n, m):   
    new_x, new_y = 0, 0
    if ni < 0:
        new_x = n - 1
    else:
        new_x = ni % n
    
    if nj < 0:
        new_y = m - 1
    else:
        new_y = nj % m
    
    return new_x, new_y

def bfs(loc, dir, grid, n, m):
    q = deque()
    visited = set()
    dx, dy = [-1,0,1,0], [0,1,0,-1]
    
    x, y = loc // m, loc % m
    visited.add((loc, dir)) ## 방문 저장
    q.append((x, y, dir))
    
    while q:
        i, j, di = q.popleft()
            
        if grid[i][j] == 'L':
            if di == 0:
                di = 3
            else:
                di -= 1

        elif grid[i][j] == 'R':
            di = (di + 1) % 4

        ni = i + dx[di]
        nj = j + dy[di]
        ## 좌표가 0 <= ni,nj < n 을 벗어나는 경우를 대비해 좌표 처리 
        ni, nj = trans(ni, nj, n, m) 
        temp = ni * m + nj
        if (temp, di) in visited:
            return visited
        visited.add((temp, di))
        q.append((ni,nj, di))
        
def solution(grid):
    answer = []
    n, m = len(grid), len(grid[0])
    
    visited = [[0,0,0,0] for _ in range(n*m)]
    
    for i in range(n*m):
        for j in range(4):
        	## 방문 확인 통해 불필요한 순회 방지
            if visited[i][j]:
                continue
            result = bfs(i,j, grid, n , m)
            answer.append(len(result))
            ## 방문 처리
            for x, y in result:
                visited[x][y] = 1
    answer.sort()
    return answer

수정 코드 (굳이 bfs가 아닌 반복문으로 해결가능)

def solution(grid):
    n, m = len(grid), len(grid[0])
    answer = []
    dx = [-1, 0, 1, 0]  # 위, 오른쪽, 아래, 왼쪽
    dy = [0, 1, 0, -1]

    visited = [[[False]*4 for _ in range(m)] for _ in range(n)]

    for x in range(n):
        for y in range(m):
            for d in range(4):
                if not visited[x][y][d]:
                    cnt = 0
                    i, j, dir = x, y, d
                    while not visited[i][j][dir]:
                        visited[i][j][dir] = True
                        cnt += 1

                        # 현재 위치에서 방향 변경
                        if grid[i][j] == 'L':
                            dir = (dir - 1) % 4
                        elif grid[i][j] == 'R':
                            dir = (dir + 1) % 4

                        # 다음 위치로 이동 (격자판을 벗어나면 반대쪽으로 이동)
                        i = (i + dx[dir]) % n
                        j = (j + dy[dir]) % m
                    answer.append(cnt)
    return sorted(answer)