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

1. 아이디어

grid의 길이가 전체 칸의 행의 길이, grid안 의 문자열 길이가 전체 칸의 열 길이와 같다. 예를 들어, grid가 ["SR". "LR"]이면 그래프는 아래와 같다.

S	L
L	R

그 다음 고려해야할 것은 방향이다. 예를 들어 초기 진입으로 1행 1열에 해당하는 S에 들어갈 때, ↓방향으로 S에 진입 또는 →방향으로 S에 진입하는 경우가 있다. 다시말해, 방향을 고려하며 각 칸에 대한 방문 여부를 처리를 해야한다.

S에 방문을 했으면, 어디로 가야할 지 결정해야한다. 이 때, S에 들어온 방향을 고려해야 한다. 예를들어 ↓방향으로 S에 들어왔으면, 다음으로 갈 칸은 2행 1열에 해당하는 L이다. →방향으로 S에 들어왔으면, 다음으로 갈 칸은 1행 2열에 해당하는 L이다. 그리고 그 다음으로 가야할 곳을 문제의 조건을 고려하여 정한다.

위의 과정을 bfs로 구현한다. 어떤 방향으로 어떤 칸을 처음 방문할 때마다, 방문한 칸 수를 증가시킨다.(방향 고려) 어떤 방향으로 어떤 칸을 재방문하게 되면, bfs를 중단하고 지금까지 세어본 칸 수를 리스트에 저장한다.

2. 코드

from collections import deque

visited = []
r, c = 0, 0
NORTH = 0
SOUTH = 1
EAST = 2
WEST = 3

def get_next_step(to, y, x):
    if to == NORTH: return y-1, x
    elif to == SOUTH: return y+1, x
    elif to == WEST: return y, x-1
    else: return y, x+1
    
def get_next_to(to, ny, nx, grid):
    if to == NORTH:
        if grid[ny][nx] == 'L': return WEST
        elif grid[ny][nx] == 'S': return NORTH
        elif grid[ny][nx] == 'R': return EAST
    
    elif to == SOUTH:
        if grid[ny][nx] == 'L': return EAST
        elif grid[ny][nx] == 'R': return WEST
        else: return SOUTH
    
    elif to == EAST:
        if grid[ny][nx] == 'L': return NORTH
        elif grid[ny][nx] == 'R': return SOUTH
        else: return EAST
    
    else:
        if grid[ny][nx] == 'L': return SOUTH
        elif grid[ny][nx] == 'R': return NORTH
        else: return WEST

def bfs(grid, sy, sx, sto):
    global r, c, visited
    visited[sy][sx][sto] = True
    q = deque()
    cnt = 1
    q.append((sy, sx, sto, cnt))
    
    while q:
        y, x, to, cnt = q.popleft()
        ny, nx = get_next_step(to, y, x)
        if ny <= -1: ny = r-1
        elif ny >= r: ny = 0

        if nx <= -1: nx = c-1
        elif nx >= c: nx = 0
        nto = get_next_to(to, ny, nx, grid)
        
        if visited[ny][nx][nto]: return cnt
        visited[ny][nx][nto] = True
        q.append((ny, nx, nto, cnt+1))
            
def solution(grid):
    global visited, r, c
    r = len(grid)
    c = len(grid[0])
    visited = [[[False for _ in range(4)] for _ in range(c)] for _ in range(r)]
    answer = []
    for i in range(r):
        for j in range(c):
            for k in (NORTH, SOUTH, EAST, WEST):
                if not visited[i][j][k]: answer.append(bfs(grid, i, j, k))
    
    answer.sort()
    return answer