Coding Test/programmers

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

파송송 2023. 3. 8. 10:58
728x90

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


나의 풀이

  • 각 칸마다 S, L, R이 적여있고 이 격자 빛을 쏘았을 때 몇 개의 사이클이 있고, 각 사이클의 길이가 얼마인지 알고 싶음
  • ["SL", "LR"]가 있을 때 [16]이 나온다.

  • DFS에서 사용하는 check를 활용하여 문제를 해결하고자 함

모든 경로를 탐색해야 하기 때문에 각 입구를 list로 만들어서 check 하는 형식으로 똑같은 곳에 사이클이 생기는 것을 방지했다.

  • S, L, R 구현을 위해 각 경우의 수에 따라 if문을 이용하려 했지만 L은 시계방향으로 R은 반시계 방향으로 이동하는 성질을 활용하여 반시계 방향으로 x, y 배열을 만듦

위와 같이 설계하고 모든 사이클을 탐색하는 코드를 작성함


def solution(grid):
    mx = (1, 0, -1, 0)
    my = (0, -1, 0, 1)

    lx, ly = len(grid[0]), len(grid)

    grid = [list(i) for i in grid]
    grid_check = [[[True]*4 for _ in range(lx)] for _ in range(ly)]

    answer = list()

    cnt = 0

    for y in range(ly):
        for x in range(lx):
            for i in range(4):
                if grid_check[y][x][i] == False:
                    pass
                else:
                    cnt = 0
                    nx, ny, ni = x, y, i
                    while grid_check[ny][nx][ni]:
                        grid_check[ny][nx][ni] = False
                        cnt += 1

                        if grid[ny][nx]=="S":
                            pass
                        elif grid[ny][nx] == "L":
                            ni = (ni - 1) % 4
                        elif grid[ny][nx] == "R":
                            ni = (ni + 1) % 4

                        ny = (ny + my[ni]) % ly
                        nx = (nx + mx[ni]) % lx

                    answer.append(cnt)
    answer = sorted(answer)
    return answer

728x90