문제

https://www.acmicpc.net/problem/2206

나의 코드 (답안 참조)

"""
1. 아이디어
사용자에게 입력받은 map은 벽이 있는지, 없는지 참고하는 용도로만 사용하고 따로 3차원 배열을
생성해서 실제 거리가 계산되어 지게끔 한다. 3차원 배열을 만들어서 bfs로 풀 수 있는가 라는게
이 문제의 핵심인거 같다.

2. 시간복잡도
O(NM)이다. 간선은 상수니깐 무시하고 정점만 세면 된다. 
3차원 배열을 만들었다고 시간복잡도가 달라지는건 없다.
어차피 여기서 BFS가 돌아가는건 2차원 배열 만들때랑 똑같다.
"""

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

n, m = map(int, input().split())
map = [ list(input().rstrip()) for _ in range(n) ]
# 실제 거리가 계산되는 map (3차원 배열이므로 생성할 때 주의)
real_map = [ [[0] * m for _ in range(n)] for _ in range(2) ] 

real_map[1][0][0] = 1 # 문제에 시작하는 칸도 포함해서 세라고 했으므로 1을 대입해준다.
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
q = deque([(1, 0, 0)]) # (1, 0, 0) 여기서 1은 벽을 부술 수 있는 기회가 있다는 것이다.
answer = -1

while q:
    wall, px, py = q.popleft()

    if px == n-1 and py == m-1: # 최종 목적지에 도착하면 세어 왔던 거리를 return한다.
        answer = real_map[wall][px][py]
        break

    for k in range(4):
        mx = px + dx[k]
        my = py + dy[k]

        if 0 <= mx < n and 0 <= my < m:
            
            # 벽을 만났지만 벽을 부술 수 있는 기회가 있을 때
            if map[mx][my] == '1' and wall == 1: 
                real_map[0][mx][my] = real_map[1][px][py] + 1
                q.append((0, mx, my))

			# 길이 뚫려 있을 때
            elif map[mx][my] == '0' and real_map[wall][mx][my] == 0:
                real_map[wall][mx][my] = real_map[wall][px][py] + 1
                q.append((wall, mx, my))

print(answer)
    

참고사항

느낀점

3차원 배열을 도입해서 bfs를 풀어야 하므로 헷갈리는 부분이 많았음.