[백준][Python]6087번(레이저 통신)

백준 6087번

✔️ 문제 풀이

• 처음에는 방문 체크를 위한 visited 배열을 deepcopy로 큐에 삽입했는데, 채점을 돌리자마자 메모리초과 발생
• visited를 큐에 삽입하는 이상 메모리초과는 해결될 수 없다고 판단해서 문제풀이 방식을 변경
  .

◾ DP 활용

• visited를 큐에 전달하지 않고, 3차원 배열로 선언하여 각 방향으로부터 오는 케이스들의 방향전환 횟수를 업데이트한다.
• 가고자 하는 좌표로 갈 때 방향전환이 필요한지 어떻게 판단할까?
  => (x, y)의 visited 값 중 최소값(최소 방향 전환)이 지금 나아가려는 방향의 visited 값과 일치한다면, 방향전환이 필요 없음
  ex) visited[y][x] 값이 [100000, 1, 1, 10000]일 때, 나아가려는 방향이 오른쪽이나 위쪽이라면 방향전환할 필요가 없기 때문에 그대로 1로 visited[ny][nx][i] 값을 업데이트한다.
  하지만 왼쪽이나 아래쪽으로 나아가려고 한다면 방향전환이 필요하다. 따라서 min(visited[y][x]) 값에서 1을 더해준 값으로 visited[ny][nx][i] 값을 업데이트한다.
• 접근하려는 좌표가 끝점 C이면(시작점 C는 어차피 재방문할 수 없음) 큐에 값을 넣지 않고, 벽이면 큐에 값을 넣는다.
• 큐가 비고, BFS가 종료되면 끝점 C의 visited 값 중 최소값을 출력한다.

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
c = []

grid = []
for i in range(m):
  row = list(input().rstrip())
  for j in range(n):
    if row[j] == 'C':
      c.append((j, i))
  grid.append(row)

visited = [[[10000,10000,10000,10000] for _ in range(n)] for _ in range(m)]
visited[c[0][1]][c[0][0]] = [0, 0, 0, 0]

q = deque()
q.append(c[0])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:

  x, y = q.popleft()
  value = min(visited[y][x])
  
  for i in range(4):

    nx = dx[i] + x
    ny = dy[i] + y

    if nx < 0 or nx >= n or ny < 0 or ny >= m:
      continue

    if grid[ny][nx] == '*':
      continue

    if value == visited[y][x][i]:
      if visited[ny][nx][i] > value:
        visited[ny][nx][i] = value
        if grid[ny][nx] == '.':
          q.append((nx, ny))
    else:
      if visited[ny][nx][i] > value+1:
        visited[ny][nx][i] = value+1
        if grid[ny][nx] == '.':
          q.append((nx, ny))
    

print(min(visited[c[1][1]][c[1][0]]))

✔️ 실행 결과

• DP를 접목해 푼게 훨씬.. 정말 훠어어어어얼씬 빠르다.. 말도 안되게 빠르다....