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

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

프로그래머스

풀이

레벨2 문제라고 만만히 봤다가 큰 코 다쳤다. 그냥 단순한 시뮬레이션 문제일줄 알았지만, 생각보다 많이 헤맸다. 관건은 문제를 이해하는데에 있었는데, 처음에는 사이클의 의미에 대해서 어떻게 구현할지 몰랐다. 생각을 해본 결과 처음에 시작했던 좌표와 방향이 같으면 그것이 하나의 사이클이라는 것을 생각하게 되었다. 또한 만약에 앞에서 방문한 방향을 타는 순간 앞에서 진행했던 사이클과 같은 노선을 탄다는 점에서, 방문 처리하는 리스트에서 참인 값을 만나는 순간 바로 정지하게 하였다. 그리고 처음에 탐색할 때부터 만약에 이미 방문한 적있는 좌표/방향이면 아예 탐색을 하지 않고, 만약 방문했던 노드인데 처음 좌표와 방향이 같다면, 사이클을 의미하므로 cnt해준 값을 answer 리스트에 넣어주었다. 모든 노드를 방문해야 사이클이라고 생각해서 모든 노드 방문 처리를 해주었던 점에서 헤매서 시간을 많이 잡아먹었다. 문제에서 주어주지 않았다면 혼자 너무 깊게 생각하지 말자ㅠ

ps. 문제를 제대로 읽자!(오름차순 잊지말기)

from collections import deque
def overlap(x, y, d):
    nx = x + dx[d]
    ny = y + dy[d]
    if nx == -1:
        nx = n-1
    if nx == n:
        nx = 0
    if ny == -1:
        ny = m-1
    if ny == m:
        ny = 0
    return nx, ny
def solution(grid):
    answer = []
    global dx, dy,n, m
    n, m = len(grid), len(grid[0])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    visited = [[[False]*4 for _ in range(m)]for _ in range(n)]
    for i in range(n):
        for j in range(m):
            q = deque()
            for k in range(4):
                if not visited[i][j][k]:
                    q.append([i, j, k])
                    visited[i][j][k] = True
                    cnt = 0
                    while q:
                        x, y, direct = q.popleft()
                        cnt += 1
                        if grid[x][y]== "S":
                            nx, ny = overlap(x, y, direct)
                        elif grid[x][y] == 'L':
                            direct -= 1
                            if direct == -1:
                                direct = 3
                            nx, ny = overlap(x, y, direct)
                        else:
                            direct += 1
                            if direct == 4:
                                direct = 0
                            nx, ny = overlap(x, y, direct)
                        if visited[nx][ny][direct]:
                            if nx == i and ny == j and direct == k:
                                answer.append(cnt)
                            break
                        q.append([nx, ny, direct])
                        visited[nx][ny][direct] = True
    answer.sort()
    return answer