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

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

프로그래머스

 

문제 설명

빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 
예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 
각 사이클의 길이가 얼마인지 알고 싶습니다. 
경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 
주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 
오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

---

제한사항

1 ≤ grid의 길이 ≤ 500
1 ≤ grid의 각 문자열의 길이 ≤ 500
grid의 모든 문자열의 길이는 서로 같습니다.
grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

---

grid = ["SL", "LR"]
# result = [16]

answer = []
vector = [[1,0],[0,1],[-1,0],[0,-1]]
v = {"S": 0,"R": -1,"L": 1}
box = [len(grid),len(grid[0])]
point_path = set()
for i in range(box[0]):
    for j in range(box[1]):
        for k in range(4):
            point = [i,j,k]
            count = 0
            while tuple(point) not in point_path:
                point_path.add(tuple(point))
                point[0] = (point[0]+vector[point[2]][0]) % box[0]
                point[1] = (point[1]+vector[point[2]][1]) % box[1]
                point[2] = (point[2]+v[grid[point[0]][point[1]]]) % 4
                count+=1
                if point == [i,j,k]: break
            if count != 0: answer.append(count)
answer.sort()

print(answer)

고민했던 부분은 중복체크였다.

 

처음 [0,0,0]으로 시작해서 루프를 한번 돌면 경로가 point_path에 저장되는데

처음엔 point_path, point 모두 list형태로 넣었더니 in에서 시간초과됐다.

 

그래서 집합 자료형을 사용했다. set은 해시 테이블 기반 데이터 구조라서 중복이 허용되지 않고,

데이터를 검색할때 O(1)의 시간복잡도를 가지기 때문에 이런 유형의 문제에서 유리하다.

그리고 set은 immutable한 원소를 넣어야하므로 list를 tuple로 변경해서 넣어줬다.

 

# 제출용 함수
def solution(grid):
    answer = []
    vector = [[1,0],[0,1],[-1,0],[0,-1]]
    v = {"S": 0,"R": -1,"L": 1}
    box = [len(grid),len(grid[0])]
    point_path = set()
    for i in range(box[0]):
        for j in range(box[1]):
            for k in range(4):
                point = [i,j,k]
                count = 0
                while tuple(point) not in point_path:
                    point_path.add(tuple(point))
                    point[0] = (point[0]+vector[point[2]][0]) % box[0]
                    point[1] = (point[1]+vector[point[2]][1]) % box[1]
                    point[2] = (point[2]+v[grid[point[0]][point[1]]]) % 4
                    count+=1
                    if point == [i,j,k]: break
                if count != 0: answer.append(count)
    answer.sort()
    return answer