Point 💡

• 처음 설계를 했을 때는 최단경로이니까 벽 1개를 부수고 가는 모든 경우의 수와 벽을 부시지않고 가는 모든 경우의 수를 구해서 가장 작은 값을 구해야한다고 생각했다. 그래서 백트래킹을 생각했는데 시간 초과의 우려가 있었다.

  → 그렇다면 어떻게 처리할까?

  • 가장 중요한 포인트는 벽을 부쉈는지 여부를 추가해 3차원 행렬로 표현해서 벽을 부수지 않은 경로에서의 개수, 벽을 부순 경로에서의 개수를 따로 저장한다.

  # index 0 : 벽을 부수지 않은 경로의 개수, index 1 : 벽을 부순 경로의 개수
  visited = [[[0, 0] for _ in range(m)] for _ in range(n)]
  
  # 3차원 행렬 (첫 시작 노드는 벽을 부수지않은 경로에 개수 1 설정)
  visited[0][0][0] = 1
  

  • bfs는 두 지점사이의 최단 경로를 구해주기 때문에 (n-1,m-1) 좌표에 도착했을 때 벽을 부순 경우가 queue에 **먼저** 들어온다면, 그 경우가 최단 경로가 되는 것이다!

• 입력값이 split 되어있지 않아서 문자열 리스트로 받고, map을 사용해서 다시 int로 변환하였다.

My Solution

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = []

for _ in range(n):
    raw = list(map(int, list(sys.stdin.readline().rstrip())))
    graph.append(raw)

# 중간에 벽을 단 한번만 부술 수 있으므로 벽을 부쉈는지 여부를 3차원 행렬로 표현
# z가 0이면 벽을 파괴할 수 있고, z가 1이면 불가능
# 벽을 부수지 않은 경로, 벽을 부순 경로
visited = [[[0, 0] for _ in range(m)] for _ in range(n)]

# 처음 시작 노드 포함이므로 벽을 부수지않은 경로에 개수 1로 설정
visited[0][0][0] = 1

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

# 최단경로 -> bfs
def bfs(x, y, z):
    queue = deque([(x, y, 0)])

    while queue:
        cur_x, cur_y, cnt = queue.popleft()

        # 끝 점에 도달하면 이동 횟수를 출력
        if cur_x == n-1 and cur_y == m-1 :
            return visited[cur_x][cur_y][cnt]

        for i in range(4):
            nx, ny = cur_x + dx[i], cur_y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 다음 이동할 곳이 벽이 아니고, 아직 한번도 방문하지 않은 곳이면
                # 벽 파괴기회를 한번 사용하면 계속 cnt는 1 (index가 1인 곳에 계속 개수 저장)
                if graph[nx][ny] == 0 and visited[nx][ny][cnt] == 0 :
                    visited[nx][ny][cnt] = visited[cur_x][cur_y][cnt] + 1
                    queue.append((nx, ny, cnt))

                # 다음 이동할 곳이 벽이고, 벽 파괴기회를 사용하지 않은 경우
                elif graph[nx][ny] == 1 and cnt == 0 :
                    # 벽을 부순 경로에 개수 추가
                    visited[nx][ny][1] = visited[cur_x][cur_y][0] + 1
                    queue.append((nx, ny, 1))

    return -1

print(bfs(0, 0, 0))

BackTracking Solution (Time-Over)

# 연구소 문제와 비슷하게 풀이

from collections import deque
import sys
input = sys.stdin.readline
def bfs():
    queue = deque()
    trial = [item[:] for item in grid]

    queue.append([0, 0])

    while queue:
        if trial[n-1][m-1] != 0:
            break
        y, x = queue.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if ny <= -1 or ny >= n or nx <= -1 or nx >= m:
                continue
            if trial[ny][nx] == 0:
                trial[ny][nx] = trial[y][x] + 1
                queue.append([ny, nx])

    global answer
    if trial[n-1][m-1] >= 1:
        answer = min(answer, trial[n-1][m-1])

def breakWall():
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                grid[i][j] = 0
                bfs()
                grid[i][j] = 1

n, m = map(int, input().split())
grid = []
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

for _ in range(n):
    grid.append(list(map(int, input().strip())))

answer = float("inf")

bfs()
breakWall()

if n == 1 and m == 1:
    print(1)
elif answer == float("inf"):
    print(-1)
else:
    print(answer+1)