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

빛의 경로 사이클

프로그래머스

 

 

• 내 첫 풀이- fail
  • 예제는 통과하는데 테스트 다 틀림 --...
  • 일단 문제가 1,1에서만 시작하는거라고 이해했는데 그게 아니고 완탐이었음
    • 문제 설명이 이상한거 아닌가..
  • 0으로 겉을 두르고 확인
    • -> 오히려 0일때 값을 그대로 넘기는 과정에서 에러가 나는 듯함

from collections import deque
answer = []

def solution(grid):
    # 동남서북
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    n = len(grid) + 2
    m = len(grid[0]) + 2

    graph = [[0 for _ in range(m)]]
    for g in grid:
        graph.append([0] + list(g) + [0])
    graph.append([0 for _ in range(m)])

    def bfs(i, j, direction, n, m):
        global answer
        queue = deque()
        
        queue.append((i, j, direction))
        visited[i][j][direction] = 0
        
        while queue:
            x, y, cur = queue.popleft()

            if graph[x][y] == "L":
                nxt = (cur + 3) % 4
            elif graph[x][y] == "R":
                nxt = (cur + 1) % 4
            else:  # "S" 또는 0일 때
                nxt = cur

            nx = (x + dx[nxt]) % n
            ny = (y + dy[nxt]) % m


            if visited[nx][ny][nxt] != -1:
                if (nx, ny, nxt) == (i, j, direction):
                    answer.append(visited[x][y][cur] + 1)
                return

            if graph[nx][ny]==0:
                visited[nx][ny][nxt] = visited[x][y][cur]
            else:
                visited[nx][ny][nxt] = visited[x][y][cur] + 1
            queue.append((nx, ny, nxt))

    # 동남서북
    visited = [[[-1, -1, -1, -1] for _ in range(m)] for _ in range(n)]
    for d in [0, 1, 2, 3]:
        if -1 not in visited[1][1]:
            continue
        bfs(1, 1, d, n, m)

    
    return sorted(answer)

 

 

• 풀이 수정 - success
  • 0으로 두르고 확인할 필요 없음
    • 오히려 0일때 값을 넘기는 과정에서 에러가 나는 듯함

from collections import deque
answer = []

def solution(grid):
    # 동남서북
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    n = len(grid)
    m = len(grid[0])

    visited = [[[-1] * 4 for _ in range(m)] for _ in range(n)]

    def bfs(i,j, direction):
        steps = 0
        queue = deque([(i, j, direction)])

        visited[i][j][direction] = steps

        while queue:
            x, y, cur= queue.popleft()
            steps += 1

            if grid[x][y] == 'L':
                nxt = (cur + 3) % 4
            elif grid[x][y] == 'R':
                nxt = (cur + 1) % 4
            else:
                nxt=cur

            nx= (x + dx[nxt]) % n
            ny= (y + dy[nxt]) % m

            if visited[nx][ny][nxt] != -1:
                answer.append(steps)
                return

            visited[nx][ny][nxt] = steps
            queue.append((nx, ny, nxt))

    for i in range(n):
        for j in range(m):
            for d in range(4):
                if visited[i][j][d] == -1:
                    bfs(i, j, d)

    return sorted(answer)