프로그래머스 - 빛의 경로 사이클 (python)

빛의 경로 사이클

코딩테스트 연습 - 빛의 경로 사이클

링크

[ 문제에 대한 이해 ]

• 어떠한 격자에서 빛을 쏜다.
• 격자에 적힌 알파벳에 따라 이동 방향이 달라진다.
• 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알아야 한다.

접근 방법

[ 어떤 칸에서부터 시작해야 할까? ]

모르면 일단 아무 지점에서 사이클을 만들어보자. → 모든 지점에서 완전 탐색을 해보자.

• 참고로, 사이클 특성 상 가장 첫 번째 위치에서만 탐색을 하더라도 모든 사이클의 파악이 가능하다. 모든 지점, 모든 방향에 대해 방문할 수 있다.
• 동일한 사이클의 기준
  • y, x 좌표에서 d 방향으로 이동한 이력이 있다면, 이미 사이클이 만들어졌다는 뜻이므로 더 이상 탐색할 필요가 없다.
  • 해당 지점에서 SLR에 따른 방향으로 이동할 경우 뒤 이동 경로는 동일하기 때문이다.

[ 탐색 방법 ]

• 시작 지점, 시작 방향에 도착했다면 하나의 사이클이 완성된 것이다.
• 방문과 동시에 사이클의 길이를 기록할 수 있도록, visited 배열을 boolean 값으로 저장하는 것 보다는, 숫자로 저장하는 것이 좋다.

1. 모든 지점 및 모든 방향에 대해 탐색할 수 있도록 3차원 배열을 준비한다.
2. 모든 지점 및 방향에 대해 탐색한다. 단, 아직 방문하지 않은 지점 및 방향이어야 한다. visited[y][x][d] == 0
3. bfs 후 해당 칸의 visited 값을 배열에 추가한다.
4. 오름차순으로 사이클 배열을 정렬한다.

• 통과 코드

  from collections import deque
  
  def bfs(sy, sx, sd, row, col, grid, visited):
      que = deque()
      dy = [row - 1, 0, 1, 0]
      dx = [0, col - 1, 0, 1]
      que.append((sy, sx, sd, 0))
      while que:
          y, x, d, cnt = que.popleft()
  
          if grid[y][x] == "S":
              nd = d
              ny = (y + dy[nd]) % row
              nx = (x + dx[nd]) % col
  
          elif grid[y][x] == "L":
              nd = (d + 1) % 4
              ny = (y + dy[nd]) % row
              nx = (x + dx[nd]) % col
  
          else:
              nd = (d + 3) % 4
              ny = (y + dy[nd]) % row
              nx = (x + dx[nd]) % col
  
          if not visited[ny][nx][nd]:
              visited[ny][nx][nd] = cnt + 1
              que.append((ny, nx, nd, cnt + 1))
  
  def solution(grid):
      answer = []
      row = len(grid)
      col = len(grid[0])
      visited = [[[0 for _ in range(4)] for _ in range(col)] for _ in range(row)]
      for y in range(row):
          for x in range(col):
              for i in range(4):
                  if not visited[y][x][i]:
                      bfs(y, x, i, row, col, grid, visited)
                      answer.append(visited[y][x][i])
      answer.sort()
      return answer
  

배운 것

• visited 배열은 boolean 값이 아닌 int 자료형으로도 구현이 가능하다.
• 이 경우, 가장 첫 번째 방문한 지점은 방문 처리가 되지 않고 다시 돌아왔을 때 방문 처리가 되기 때문에 사이클 처리에 더 용이하다.