백준 구현 대비 구슬이동2

접근

재귀 dfs+구현으로 풀이 재귀의 깊이가 10이 넘어가거나 빨간색공 파란색공이 구멍에 빠지게 되면 return
동서남북 각각 4방향으로 분기를 나눠주어 dfs진행한다. 이때 두 구슬은 동시에 움직이므로 각각의 위치마다 우선순위를 부여해주어야함. 예를들어 왼쪽으로 기울이는 상황에서는 왼편에 있는 구슬이 먼저 움직이고, 그 반대 상황에서는 반대의 구슬이 먼저 움직이도록 구현해야함.

대충시간복잡도를 계산했을때 Nx4^10===Nx1000000이라서 당연히 통과할 줄 알았으나 실행시간이 너무 오래걸림. 뭐가 문제인지 봤더니 deepcopy쪽에서 시간을 너무 잡아먹고 있었음

리스트의 깊은복사에는 두가지 방식이 대표적으로 사용된다.
1. slicing
2. deepcopy
이들 중 deepcopy함수가 slicing보다 100배정도 더 느린 속도를 보여줌. 그 이유는 deepcopy함수는 객체의 모든 속성을 복사해옴. 반면에 slicing은 리스트의 요소 갯수만큼의 시간복잡도를 가짐. 따라서 앞으로 연산횟수가 거대한 코드를 짤때에는 deepcopy보다 다음과 같은 슬라이싱 방식을 사용하도록 하자

list_a = [[i for i in range(100)] for _ in range(100)]
list_b = []
list_b = [item[:] for item in list_a]

출처:https://velog.io/@emplam27/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EA%B9%8A%EC%9D%80%EB%B3%B5%EC%82%AC%EB%8A%94-deepcopy%EA%B0%80-%EB%B9%A0%EB%A5%BC%EA%B9%8C-slicing%EC%9D%B4-%EB%B9%A0%EB%A5%BC%EA%B9%8C

코드

import copy

N,M=map(int, input().split())
graph=[]
answer=11
rr=0
movelist=['L','R','U','D']

def move(graph,curi,curj,dir):
  global N,M
  while True:
    if dir=='L':
      ni,nj=curi,curj-1
    elif dir=='R':
      ni,nj=curi,curj+1
    elif dir=='U':
      ni,nj=curi-1,curj
    else:
      ni,nj=curi+1,curj
    if 1<=ni<N-1 and 1<=nj<M-1:
      if graph[ni][nj]=='.':
        graph[curi][curj] , graph[ni][nj] = graph[ni][nj] , graph[curi][curj] 
        curi,curj=ni,nj
      elif graph[ni][nj]=='O':
        graph[curi][curj]='.'
        return [ni,nj]
      else:
        return[curi,curj]
    else:
      return [curi,curj]


def dfs(graph,bi,bj,ri,rj,dir,count):
  global answer
  if dir=='L':
    if bj<=rj:
      b=move(graph,bi,bj,dir)
      r=move(graph,ri,rj,dir)
    else:
      r=move(graph,ri,rj,dir)
      b=move(graph,bi,bj,dir)

  elif dir=='R':
    if bj>rj:
      b=move(graph,bi,bj,dir)
      r=move(graph,ri,rj,dir)
    else:
      r=move(graph,ri,rj,dir)
      b=move(graph,bi,bj,dir)

  elif dir=='D':
    if bi>=ri:
      b=move(graph,bi,bj,dir)
      r=move(graph,ri,rj,dir)
    else:
      r=move(graph,ri,rj,dir)
      b=move(graph,bi,bj,dir)

  else:
    if bi<ri:
      b=move(graph,bi,bj,dir)
      r=move(graph,ri,rj,dir)
    else:
      r=move(graph,ri,rj,dir)
      b=move(graph,bi,bj,dir)
  if graph[b[0]][b[1]]=='O':
    return
  elif graph[r[0]][r[1]]=='O':
    answer=min(answer,count)
    return
  elif count==10:
    return
  else:
    for mo in movelist:
      tempgraph=[]
      tempgraph=[item[:] for item in graph]
      dfs(tempgraph,b[0],b[1],r[0],r[1],mo,count+1)
  
for i in range(N):
  graph.append(list(input()))
bi,bj,ri,rj=0,0,0,0
for i in range(N):
  for j in range(M):
    if graph[i][j]=='B':
      bi,bj=i,j
    elif graph[i][j]=='R':
      ri,rj=i,j


for mo in movelist:
  tempgraph=[]
  tempgraph=[item[:] for item in graph]
  dfs(tempgraph,bi,bj,ri,rj,mo,1)

if answer>10:
  print(-1)
else:
  print(answer)