프로그래머스 [Lv. 2] 빛의 경로 사이클 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드 1

def solution(grid):
    answer = []
    
    n = len(grid)
    m = len(grid[0])
    
    dr = [-1, 0, 1, 0] # 상 우 하 좌
    dc = [0, 1, 0, -1]
    visited = dict()
    
    for r in range(n):
        for c in range(m):
            for d in range(4):
                cnt = 0
                nr = r
                nc = c
                nd = d
                while True:
                    key = f"{nr},{nc},{nd}" # r, c로 빛이 d방향에서 들어온다
                    if visited.get(key):
                        break
                    cnt += 1
                    visited[key] = 1
                    string = grid[nr][nc]
                    if string == "L":
                        nd = (nd - 1) % 4
                    elif string == "R":
                        nd = (nd + 1) % 4
                    
                    nr = (nr + dr[nd]) % n
                    nc = (nc + dc[nd]) % m
                if cnt:
                    answer.append(cnt)
    answer.sort()
    return answer

정답 코드 2

def solution(grid):
    answer = []
    
    n = len(grid)
    m = len(grid[0])
    
    dr = [-1, 0, 1, 0] # 상 우 하 좌
    dc = [0, 1, 0, -1]
    visited = [[[0] * 4 for _ in range(m)] for _ in range(n)]
    
    for r in range(n):
        for c in range(m):
            for d in range(4):
                cnt = 0
                nr = r
                nc = c
                nd = d
                while not visited[nr][nc][nd]:
                    cnt += 1
                    visited[nr][nc][nd] = 1
                    string = grid[nr][nc]
                    if string == "L":
                        nd = (nd - 1) % 4
                    elif string == "R":
                        nd = (nd + 1) % 4
                    
                    nr = (nr + dr[nd]) % n
                    nc = (nc + dc[nd]) % m
                if cnt:
                    answer.append(cnt)
    answer.sort()
    return answer

풀이 방법

• 정답 코드 2의 풀이는 다음과 같다.
  • https://sound-programming.tistory.com/216

프로그래머스 [Lv. 2] 빛의 경로 사이클 {언어 : JavaScript} [다시 풀어 보기]

1. visited를 딕셔너리 형태로 만들었다.
2. 현재 격자 S L R에 들어오는 빛의 방향을 visited에 저장하면 되겠구나 생각했다.
3. key를 nr, nc, nd로 만들어서 저장시켰다.
4. L인 경우 현재 nd에서 왼쪽으로 가야하므로 -1을 빼주고 4로 나누어 떨어진 수로 치환했다.
5. R인 경우 현재 nd에서 오른쪽으로 가야하므로 1을 더해주고 4로 나누어 떨어진 수로 치환했다.
6. key를 다시 갱신시키고 while문을 이어가면서 cnt에 1을 더해준다.
7. 마지막으로 cnt가 있다는 말은 순환 경로가 있다는 말이므로 answer에 저장시켰다.
8. 오름차순 정렬을 하고 answer를 반환하면 끝!

정답 코드 1의 실행 결과

정답 코드 2의 실행 결과

느낀점

• 오랜만에 다시 풀어보는데 풀이 방법이 떠오르지 않았다.
• 하지만 아! 현재 격자와 들어오는 빛의 방향을 함께 묶어서 visited에 저장하면 중복될 일이 없겠구나 싶었다.
• 풀고 보니 전에 풀었던 방식이랑 비슷했지만 dictionary로 만들어서 시간이 더 오래 걸린 것 같다.