[Algorithm] 목수의 미로 탈출

---

문제 분석

: 이전에 '미로 찾기' 문제와 똑같은 문제지만, 거기에 목수가 하나의 장애물을 부술 수 있다는 조건이 추가된 문제이다. 특정 좌표 x,y에서 z,a까지의 '최단거리'를 구하되, 중간에 1로 표현된 장애물이 있는데, 이 장애물 중에 하나를 부술 수 있는 조건이 추가된 것이다.

문제 설계

: 이미 BFS를 통해서 최단거리를 구할 수 있는 설계부분은 이전 문제에서 해봤으므로, 여기서는 장애물을 하나 부술수 있다는 조건을 어떻게 설계 및 구현해낼지를 고민해본다.

• 1을 하나 무시할 수 있음. 즉, 주어진 1중에 하나를 0으로 만들어서 그 경로를 이용할 수 있는 것임.
• BFS 설계를 할 때는 1을 인덱싱하면 그 시행은 continue로 무시했었음. 즉, 좌표에 1이 있으면 그 부분은 의미가 없는 것으로 취급했었음. 근데 이제, 그 1을 하나 부술수 있으므로 만약 1이 나오면, 무시하면 안됨.
• 생각해낸 방법은 일단 BFS로 탐색을 하는 도중에 특정 경로에서 장애물 1을 만났을 경우, 그 1에서부터(다른 탐색을 잠시 멈추고) 다시 BFS를 돌려서 최단거리를 탐색한다. 그러면, 각자 모든 탐색 경로에서 장애물 1개를 무시하고, 최단거리를 탐색해볼 수 있다. 이 때, 장애물을 부순 경우에 얻게된 최단거리는 따로 배열에 저장해둔다음에 장애물을 안부순 경우에 얻게된 최단거리와 비교해서 최종 정답을 얻어내면 되겠다.
• 시간복잡도는 안전한가?
  : 최악의 경우 1000 * 1000의 배열을 BFS로 탐색해야하는데(O(1,000,000)) 거기에 만약 장애물을 만나면 + O(N)을 해야한다. 하지만 장애물이 많아서 O(N^2)이 된다해도 그만큼 장애물이 많으면 얼마 못가서 탐색을 멈추될테고, O(N^2)까지가 아니라면 최악의 경우에 결국 O(X) 정도일테니 시간복잡도면에서 걸릴 것 같지는 않다고 판단했다.

문제 구현

import copy

n,m = map(int, input().split())
board = []
# 경계 설정을 이번엔 1로하면 장애물로 인식할 수 있으니 -1로
for i in range(n):
  board.append([-1] + list(map(int,input().split())) + [-1])
limit_line = [[-1 for i in range(m+2)]]
board = limit_line + board + limit_line

root = (n, 1) 
queue = [root]
path = {}
path[root] = 0

cheat_way = []

copy_board = copy.deepcopy(board)
copy_board[n][1] = -1

while len(queue) != 0:
  top = queue.pop(0)
  
  up = (top[0]-1, top[1])
  right = (top[0], top[1]+1)
  down = (top[0]+1, top[1])
  left = (top[0], top[1]-1)
  
  next_arr = []
  for el in [up,right,down,left] :
    if copy_board[el[0]][el[1]] == 0:
      now_len = path[top] + 1
      if now_len == 1:
        now_len = "1"
      copy_board[el[0]][el[1]] = now_len
      path[el] = path[top] + 1
      next_arr.append(el)
    elif copy_board[el[0]][el[1]] == 1:
      try:
        if path[el]:
          continue
      except:
        path[el] = True
      cheats_copy_board = copy.deepcopy(copy_board)
      # 장애물을 만났을 때 또 BFS 탐색으로 끝까지 가보기
      # 여태까지의 거리
      copy_queue = [el]

      copy_path = {}
      copy_path[el] = path[top] + 1
      cheats_copy_board[el[0]][el[1]] = path[top] + 1

      while len(copy_queue) != 0:
        copy_top = copy_queue.pop(0)

        copy_up = (copy_top[0]-1, copy_top[1])
        copy_right = (copy_top[0], copy_top[1]+1)
        copy_down = (copy_top[0]+1, copy_top[1])
        copy_left = (copy_top[0], copy_top[1]-1)

        copy_next_arr = []
        for idx in [copy_up,copy_right,copy_down,copy_left] :
          if cheats_copy_board[idx[0]][idx[1]] == 0:
            cheats_copy_board[idx[0]][idx[1]] = copy_path[copy_top] + 1
            copy_path[idx] = copy_path[copy_top] + 1
            copy_next_arr.append(idx)
          else:
            continue
        copy_queue+= copy_next_arr
      minimum = cheats_copy_board[1][m]
      if minimum != 0:
        cheat_way.append(minimum)
    else:
      continue
  queue+= next_arr

cheat_way.append(copy_board[1][m])

result = min(cheat_way)
if result == 0:
  cheat_way.remove(0)
  print(min(cheat_way))
else:
  print(result)

: 굉장히 복잡한 코드가 돼버렸는데.. 심지어 시간복잡도도 통과못했다.. 결국 못맞췄다 ㅠ

오답 풀이

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

for i in range(n):
  board.append([-1] + list(map(int,input().split())) + [-1])
limit_line = [[-1 for i in range(m+2)]]
board = limit_line + board + limit_line

root = (n, 1) 
queue = [root]
path = {}
path[root] = True
depth = {}
depth[root] = "0"
barrier = {}

copy_board = []

for row in board:
  arr = []
  for column in row:
    arr.append(column)
  copy_board.append(arr)
  
while len(queue) != 0:
  
  top = queue.pop(0)
  up = (top[0]-1, top[1])
  childs = []
  try:
    if path[up]:
      pass
  except:
    path[up]= True
    childs.append(up)
  right = (top[0],top[1]+1)
  try:
    if path[right]:
      pass
  except:
    path[right]= True
    childs.append(right)
  down = (top[0]+1,top[1])
  try:
    if path[down]:
      pass
  except:
    path[down]= True
    childs.append(down)
  left = (top[0],top[1]-1)
  try:
    if path[left]:
      pass
  except:
    path[left]= True
    childs.append(left)
  for el in childs:
    if board[el[0]][el[1]] == 1:
      # 여기서 로직
      try:
        barrier[el].append(int(depth[top]))
      except:
        barrier[el] = [int(depth[top])]
      continue
    elif board[el[0]][el[1]] == 0:
      copy_board[el[0]][el[1]] = int(depth[top]) +1 
      depth[el] = int(depth[top]) +1 
      queue.append(el)      
    else:
      continue
      
# 여기서부터 반대로 하는 BFS

reverse_root = (1,m)
reverse_queue = [reverse_root]
path = {}
path[reverse_root] = True 
depth[reverse_root] = "0"

while len(reverse_queue) != 0:
  top = reverse_queue.pop(0)
  childs = []
  
  up = (top[0]-1, top[1])
  try:
    if board[up[0]][up[1]] == -1 or path[up]:
      pass
  except:
    path[up]= True
    childs.append(up)
  right = (top[0],top[1]+1)
  try:
    if board[right[0]][right[1]] == -1 or path[right]:
      pass
  except:
    path[right]= True
    childs.append(right)
  down = (top[0]+1,top[1])
  try:
    if board[down[0]][down[1]] == -1 or path[down]:
      pass
  except:
    path[down]= True
    childs.append(down)
  left = (top[0],top[1]-1)
  try:
    if board[left[0]][left[1]] == -1 or path[left]:
      pass
  except:
    path[left]= True
    childs.append(left)

  for el in childs:
    if board[el[0]][el[1]] == 1:
      try:
        barrier[el].append(int(depth[top]))
      except:
        barrier[el] = [int(depth[top])]
      continue
    elif board[el[0]][el[1]] == 0:
      depth[el] = int(depth[top]) + 1 
      reverse_queue.append(el)
    else:
      continue

barrier_min = copy_board[1][m]
if barrier_min == 0:
  barrier_min = n*m
for arr in barrier.values():
  if len(arr) == 1:
    continue
  else:
    if sum(arr)+2 < barrier_min:
      barrier_min = sum(arr)+2
    
print(barrier_min)

---

: 간단하게 오답 풀이를 설명해보면, 일단 내 생각으로 풀지는 못했고, 힌트를 받아서 해결했다. 힌트는 나는 일단 접근 자체를 BFS를 써서 탐색을 하다가 1을 만났을 때 새로 또 BFS를 하는 방법은 시간복잡도 때문에 안되니까 일단 BFS로 최단거리를 구한 다음에 stack을 써서.. 뭐 그 최단거리에서 장애물 하나 없앤다하면 더 빨리 갈 수 있지 않을까? 이런식으로 밖에는 생각하지 못했다..ㅎ 하지만, 이걸 왼쪽 하단 꼭지점과 우측 상단 꼭지점에서, 즉, 양옆에서 탐색을 시작해서 1에서 만난다는 발상을 해보면 쉽게 풀리는 문제였다.. 왼쪽 하단에서 출발해서 1을 만났을 때까지의 거리와 우측 상단에서 출발해서 1을 만났을 때까지의 거리를 더하면 1하나를 무시한채 갈 수 있는 최단거리가 나올 것이기 때문이다. 이런식으로 1 하나를 무시한채 갈 수 있는 거리를 모두 구하고, 왼쪽 하단에서 BFS를 했을 때 구한 최단거리를 거기에 합해서 그 중에 가장 작은 수를 리턴해주면 된다. 이 때, 장애물이 아예 다막고 있는 경우가 있기에 만약에 최단거리가 0이 나오면 따로 처리를 해줘야한다.