[백준2206&파이썬] BFS에서 이동상태가 분리된다면 방문 확인도 분리시켜야 한다.

# 문제

백준 2206 벽 부수고 이동하기 파이썬

2206번: 벽 부수고 이동하기

# 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
# 1,1 과 N,M은 항상 0임
# 1,1 -> n,m 으로 이동해야함

visit = [[[False] * M for _ in range(N)] for i in range(2)] # 벽부수고 가는 경우랑 아닌경우 나눠야함

board = list()
for _ in range(N):
  line = list(str(sys.stdin.readline().strip()))
  line = list(map(int, line))  # 문자열을 정수로 바꾸기
  board.append(line)

# print(board)

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

# 시작지점은 항상 0,0 임
# 도착지점은 항상 M,N 즉 M-1,N-1 임

# 벽을 깨는 경우와 벽을 못깨는 경우를 나눠서 생각해야함

dq = deque()
dq.append((0, 0, 1, 1))  # ( 행,열,시간,벽깰 수 있는지 여부)

while len(dq) != 0:
  cur = dq.popleft()

  if cur[0] == N - 1 and cur[1] == M - 1:
    print(cur[2])  # 최종 도착하면
    exit()

  for dir in dirs:
    next_row_col = (cur[0] + dir[0], cur[1] + dir[1])


    # 범위 체크
    if 0 <= next_row_col[0] < N and 0 <= next_row_col[1] < M:
      # 다음이 벽인지 0인지
      if board[next_row_col[0]][next_row_col[1]] == 1:  # 벽이면
        if cur[3] and visit[cur[3]][next_row_col[0]][next_row_col[1]] == False:  # 아직 벽을 깨본게 아니고 방문했던 벽이 아니라면
          dq.append((next_row_col[0], next_row_col[1], cur[2] + 1, 0))
          visit[0][next_row_col[0]][next_row_col[1]] = True

      else:
        if visit[cur[3]][next_row_col[0]][next_row_col[1]] == False:
          if next_row_col[0] == N - 1 and next_row_col[1] == M - 1:
            print(cur[2] + 1)  # 최종 도착하면
            exit()

          dq.append((next_row_col[0], next_row_col[1], cur[2] + 1, cur[3]))
          visit[cur[3]][next_row_col[0]][next_row_col[1]] = True

print(-1)

 

# 풀이

## 공백없이 들어온 입력값 하나씩 쪼개 리스트로 저장하기

• 저번 풀이에서 문자열로 들어온걸 하나씩 쪼갰었다. 이번에는 공백없이 들어온 정수를 쪼개서 사용해야한다.
• 먼저 문자열로 쪼개놓고, 정수로 바꾼 뒤 정수로 다시 바꿔주는 방법을 사용하면 쉽다.

for _ in range(N):
  line = list(str(sys.stdin.readline().strip()))
  line = list(map(int, line))  # 문자열을 정수로 바꾸기
  board.append(line)

 

## 앞서나가는 것이 생기면 visit를 분리해서 관리해야 한다.

• 이 케이스를 생각은 했는데 어떻게 극복해야할지에 대해서 고민을 했었다. 
• 아래와 같은 예제 케이스를 살펴보자

2 4
0111
0010

• BFS의 특징은 같은 단계씩 밟아나가기 때문에 앞서 나가는 놈이 생기지 않는다. 
• 그러나 이번 문제에서 벽을깨고 질주하는놈이 생겨버리면 조건에 따라 앞선(?)다는 생각을 할 수 있다.
• 문제에서는 벽을 한번만 깰 수 있다. 벽을 깬놈이 최종 도착지 앞에 벽이 있어서 깨야하지만 이미 깨서 못 깨버린다면 그 경로는 잘못된 경로이다. 그렇기 때문에 visit를 처리된것을 다시 원복을 시키던가 해야한다.
• 그러나 DFS가 아니기 때문에 원복을 시킬 수는 없다.
• 그래서 나는 몇번째 방문에 따라서 visit를 3차원 배열의 형태로 만들었는데, 당연하게도 메모리 초과가 났다. 1000*1000이 들어올수 있기 떄문이다.
• 나는 큐에 넣어주는 하나의 노드 단위에 벽을 부수고 온놈인지 아닌놈인지 마킹을 해두었다. 

dq.append((0, 0, 1, 1)) # ( 행,열 , 시간, 벽깰 수 있는지 여부) 0-> 이미 깬놈, 1-> 깰 수 있음

• 그래서 벽을 만나면 일단 저 마킹 상태를 보고 깰 수 있는 놈이라면 깨도록 했다. 그리고 깬놈들만의 visit[0] 으로 시작하는 방문을 기록한다.
• 못깬놈들은 못깬놈들끼리의 cur[1]이 되는 방문배열을 하기 때문에 깬놈과 못깬놈의 진행사항에서 서로의 간섭이 일어나지 않는다.